Reminder: This post contains 1503 words
· 5 min read
· by Xianbin
The survey [1] is really beautiful and makes a well-known computer scientist.
Cell Probe Complexity Model
The cell probe model can be viewed as a sequence of \(cells\), or words, each of which contains \(w\)-bit field (normally, we assume that \(w= \Theta(\log n)\). This model only calculates the cost of an algorithm by counting the number of reads and writes, and all other computation tasks are ignored. Therefore, this model is used to prove a lower bound not an upper bound.
Dynamic connectivity Lower Bound for Paths
\(\textbf{Theorem 1}\). Under the cell prove model, the lower bound worst-case cost is \(\Omega(\log n)\) per operation.
Path Grid
It is a \(\sqrt{n}\) by \(\sqrt{n}\) grid. We use \(C_0, C_1,\ldots, C_{\sqrt{n}-1}\) to denote the columns of the grid. This grid has a perfect matching. It is easy to see that there are \(\sqrt{n}\) disjoint paths across columns. Then path can be coded by the permutations \(\pi_1,\ldots,\pi_{\sqrt{n}-1}\) where \(\pi_i\) is the permutation of edges that join column \(C_i\) and \(C_{i+1}\).
We have two operations on the grid.
- UPDATE(\(i,\pi\)). Replace the \(i\)-th permutation \(\pi\) in the grid with permutation \(\pi\). It is equal to \(\sqrt{n}\) edge deletions/insertions.
- VERIFY_SUM(\(i,\pi\)). Check if \(\sum_{j=1}^i \pi_j = \pi_1 \circ \pi_2 \circ \ldots \circ \pi_j= \pi\). It is equivalent to checking if the first \(i\) permutations is equal to a single permutation \(\pi\) (also \(\sqrt{n}\) connectivity queries).
Reference
[1]. Miltersen, Peter Bro. “Cell probe complexity-a survey.” Proceedings of the 19th conference on the foundations of software technology and theoretical computer science, advances in data structures workshop. 1999.
[2]. Advanced Data Structures by Prof. Erik Demaine.