Logarithmic lower bounds in the cell-probe model

Pat Morin

Consider the data structuring problem of maintaining a sequence A_1,...,A_n of integers with each A_i in {1,...,n} under the following two operations:

  1. Modify(i, x) : Set A_i = x (update)
  2. PartialSum(i) : Compute the sum of A_1,...,A_i (query)
The folklore solution to this problem is to maintain a balanced binary tree whose leaves (in order) store A_1,...,A_n and whose internal nodes store the sum of the values in their two children. This data structure can perform updates and queries in O(log n) time.

In this talk we will present a recent result due to Demaine and Patrascu (SICOMP 2006) which shows that the above data structure is optimal. There exists sequences of O(n) updates and searches that require Omega(n log n) time. This lower bound holds in the cell probe model of computation in which the only cost associated with an algorithm are these costs of reading and writing individual memory cells.