4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Can you clearly state the problem? Some of us don't have access to CLRS. $\endgroup$ – Yuval Filmus Jan 31 '15 at 23:29
  • $\begingroup$ I have not yet identified the flaws of your potential function. See my answer below for another possible one. However, why do you think that $O(n)$ contradicts the lower-bound of compare-based sorting? You are not sorting an array (at least not sorting a general array). $\endgroup$ – hengxin Feb 2 '15 at 4:36
  • $\begingroup$ Suppose you have inserted all $n$ elements. Then all $A_i, i = 0, \dots, k - 1$ are full. And if my proof is correct this costs $\mathcal{O}(n)$ time. Now let's insert some dummy element($-\infty$). Then all arrays $A_i, i = 0, \dots, k - 1$ will be merged in one array $A_k$ which size is $2^k \ge n$. And this array is sorted. To merge arrays $A_i, i = 0, \dots, k - 1$ we need $\mathcal{O}(n)$ time. Hence, we have sorted input using compare-based sort in $\mathcal{O}(n)$ time. This is contradiction. $\endgroup$ – rbtrht Feb 2 '15 at 10:36
  • $\begingroup$ Finally I have found a mistake in my reasoning. It was in expression for $\hat{c_i}$ in case of $r = 0$. So $\hat{c_i} \neq 3$. Correct expression is $\hat{c_i} = 1 + \Phi_i - \Phi_{i-1} = 1 + n = \mathcal{O}(n)$ where $\Phi_i \le n$, since after inserting element in empty $A_0$ $\Phi_i$ could be at most $n$(all $n_i = 1$), and $\Phi_{i-1} = 0$. But @hengxin provided correct solution for this problem and I mark his answer as correct. $\endgroup$ – rbtrht Feb 2 '15 at 21:06
  • $\begingroup$ Yes, I see now. $\endgroup$ – hengxin Feb 3 '15 at 4:33
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for answer! But I didn't understand several things: 1. Why the first bit(which corresponds to array of size 1 and $n_0$) has potential $(k - 1)$. But, in my intuition, the more long array we have the more potential we should have to move down this array. 2. Why did you write in $\sum_{i=0}^{i=t-1} 2^i (t-i)$ the term $(t - i)$ instead of $((k-1)-i)$? $\endgroup$ – rbtrht Feb 2 '15 at 13:13
  • $\begingroup$ @YaroslavAkhremtsev 1. The element at the top will be moved down to the bottom. The more higher it is, the more times it will be moved down and the more price it pays. 2. $t$ is the number of merges that caused by the inserted element. Being $t$ merges means that only the first $t$ top subarrays are involved in the insertion. Therefore, the change of the potential function can be calculated within the $t$ subarrays. $\endgroup$ – hengxin Feb 2 '15 at 13:20
  • $\begingroup$ I understand that we calculate the change of potential function only within $t$ subarrays. Hence, the change occurred in $t+1$ arrays(since we merged elements from $t$ arrays to $t+1$ array). Then $\Delta \Phi = 2^{t} * ((k - 1) - t) - \sum^{t-1}_{i=0} 2^i((k - 1)-i)$ and I don't still understand why there should be $(t - i)$ instead of $((k-1)-i)$. Could you explain more precisely please. $\endgroup$ – rbtrht Feb 2 '15 at 13:36
  • $\begingroup$ @YaroslavAkhremtsev $\sum_{i=0}^{i=t-1} 2^i (t-i)$: First each subarray $A_i, i = 0, \cdots, t-1$ contains $2^i$ elements. Secondly, each element in $A_i$ will be moved down to the $t$ level subarray $A_t$, decreasing its potential by $t-i$, i.e., from $(k-1)-i$ to $(k-1)-t$. Summing them together, we obtain the whole decrement of the potential function. $\endgroup$ – hengxin Feb 2 '15 at 13:58
  • $\begingroup$ Now I understand. Thank you. But I still don't see mistake in my solution. $\endgroup$ – rbtrht Feb 2 '15 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.