Potential method for dynamic binary search

Problem Detail: 

I'm trying to solve 17-2(b) problem from Cormen(CLRS) using potential method.

Problem from Cormen:

17-2 Making binary search dynamic Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays.

Specifically, suppose that we wish to support SEARCH and INSERT on a set of $n$ elements. Let $k = \lceil \log_2(n + 1) \rceil$, and let the binary representation of n be $\langle n_{k-1}, n_{k-2}, \dots , n_0 \rangle$. We have $k$ sorted arrays $A_0, A_1, \dots, A_{k - 1}$, where for $i = 0, 1, \dots, k - 1$, the length of array $A_i$ is $2^i$. Each array is either full or empty, depending on whether $n_i = 1$ or $n_i = 0$, respectively. The total number of elements held in all $k$ arrays is therefore $\sum^{k-1}_{i=0}n_i 2^i = n$. Although each individual array is sorted, elements in different arrays bear no particular relationship to each other.

• Describe how to perform the SEARCH operation for this data structure. Analyze its worst-case running time.
• Describe how to perform the INSERT operation. Analyze its worst-case and amortized running times.
• Discuss how to implement DELETE.

---

So I'm trying to solve point b. Working time: we have $k = \log_2(n)$ sorted arrays $A_i$ and corresponding bits $b_i$. Size of array $A_i$ is $2^i$. If it's full then $b_i = 1$ else $b_i = 0$.

If first $r$ arrays are full then we can place all elements from them to empty array $A_r$. And we need $2^{r+1} - 2$ time(we merge first arrays: $2 \cdot (2^0 + 2^1 + \dots + 2^{r-1}) = 2^{r+1} - 2$).

Let potential function be $\Phi_i = 2^{r+1} - 2$, where r is number of first bits which are 1. For example, if we have bit string 111110110101 then $r=5$. If $r = 0$ then $\Phi_i = 0$.

Now suppose that we want to calculate amortized cost $\hat{c}_i$ when first $r > 0$ bits are 1. Thus, $\hat{c}_i = 2^{r+1} - 2 + (0 - (2^{r+1} - 2)) = 0$

If $r = 0$ then $\hat{c}_i = 3$.

So we can insert $n$ elements for $\mathcal{O}(n)$ time and they will be sorted. But this is contradicts to lower bound of compare-based sorting.

Could you please help me to find a mistake in my reasoning. I know that correct amortized time is $\hat{c}_i = \mathcal{O}(\log_2(n))$ if we use account method(I found the solution).

Thank you very much!

Asked By : Yaroslav Akhremtsev

Answered By : hengxin

What about this potential function

$$\Phi = \sum_{i=0}^{k-1} n_i \cdot 2^i \cdot \left((k-1) - i \right),$$

where $k = \lceil \lg(n+1) \rceil$ (please check the details related to the stuff of $\lg$ and $\lceil \rceil$).

That is, each element in "depth" $n_i (i = 0, \cdots, k-1)$ has its "individual potential" $(k-1) - i$. The intuition is the higher the element is, the more potential it has and the higher price you pay to move it down (until the bottom). The whole potential of the data structure at any state is the sum of the potential of its all elements.

With this potential function, the amortized cost for the insertion of an element which does not cause any merge (i.e., the element is inserted into the empty subarray $A_0$) is

$$\hat{c} = 1 \quad (\text{actual cost for creation}) + (k-1) \quad (\text{increment of the potential function}) \\ = k = \lceil \lg(n+1) \rceil.$$

On the other hand, the amortized cost for the insertion of an element which causes $t$ merges is (please check the computation):

$$\hat{c} = 1 + \sum_{i=1}^{t} 2^t - (\sum_{i=0}^{i=t-1} 2^i (t-i)) \quad (\text{the potential decreases}) \\ = (2^{t+1} - 1) - (t(2^t-1) - (2^t t-2^{t+1} +2)) \\ = t + 1 \le k = \lceil \lg(n+1) \rceil.$$

Therefore, the amortized cost for each insertion is $O(\lg n)$.

---

Explanation for the decrement of the potential function $\sum_{i=0}^{i=t-1} 2^i (t-i)$:
First, each subarray $A_i,i=0,⋯,t−1$ contains $2^i$ elements. Secondly, each element in $A_i$ will be moved down to the $t$-th level subarray $A_t$, decreasing its potential by $t−i$, i.e., from $(k−1)−i$ to $(k−1)−t$. Summing them up, we obtain the total decrement of the potential function.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37822