1
$\begingroup$

I'm working through CLRS, Chapter 17 on Amortized Analysis. One of the problems I attempted to solve is 17.2-2 (described below), but my answer differs from the one in the instructor's manual, so I thought I'd solicit your feedback. I appreciate any help with this.

Problem. We have a data structure supporting some number of operations. Given a sequence of n such operations, we're to determine the amortized cost of each operation using the Accounting Method [CLRS, 17.2]. The actual cost of $i^{th}$ operation is defined as follows:

$$ cost(i) = \begin{cases} i & \text{if $i$ is an exact power of 2} \\[2ex] 1 & \text{otherwise} \end{cases} $$

Assume that exact powers of 2 form the sequence: $1, 2, 4, 8, \ldots$.

Solution. (My attempt) For the sake of concreteness, consider a sequence of 10 operations:

$$ \begin{array}{c|ccc} i & cost(i) & notes\\ \hline 1 & 1 & 1 = 2^0\\ 2 & 2 & 2 = 2^1\\ 3 & 1 &\\ 4 & 4 & 4 = 2^2\\ 5 & 1 &\\ 6 & 1 &\\ 7 & 1 &\\ 8 & 8 & 8 = 2^3\\ 9 & 1 &\\ 10 & 1 &\\ \end{array} $$

The approach is predicated on the observation, based on this data, that between consecutive power of 2 operations (say, 1 and 2 or 2 and 4 or 4 and 8, etc.) there are exactly $i-1$ unit-cost operations. For example, if $i=1$, then between operations 1 and 2 there should be $1-1 = 0$ unit-cost operations and indeed there are none. Another example, consider $i=4$. We again verify that between 4 and 8 there are $4-1 = 3$ unit-time operations.

Based on that hypothesis, we assign the following "charges" ($\widehat{cost}$) to each of the operations:

$$ \widehat{cost}(i) = \begin{cases} i + (i - 1) & \text{if $i$ is an exact power of 2} \\[2ex] \tag{$\alpha$} 0 & \text{otherwise} \end{cases} $$

The idea is that each power of 2 operation pays for itself (that's the $i$ summand) and leaves credit just enough to cover the $cost$ of the next $(i-1)$ unit-cost operations. Visually:

$$ \begin{array}{c|ccc} i & cost(i) & \widehat{cost(i)} & \text{"remaining credit"}\\ \hline 1 & 1 & 1 & 0\\ 2 & 2 & 3 & 1\\ 3 & 1 & 0 & 0\\ 4 & 4 & 7 & 3\\ 5 & 1 & 0 & 2\\ 6 & 1 & 0 & 1\\ 7 & 1 & 0 & 0\\ 8 & 8 & 15 & 7\\ 9 & 1 & 0 & 6\\ 10 & 1 & 0 & 5\\ \end{array} $$

At the end of the sequence, we're left with 5 units of credit, which will pay the price of the next 5 unit-cost operations ($i = 11, \ldots, 15$).

The amortized cost of a given operation is $i + (i - 1)$, which is bounded by $2n$. The book has a $3n$ in the analysis, so I'm wondering where I'm messing up.

$\endgroup$
  • 2
    $\begingroup$ "but my answer differs from the one in the instructor's manual" -- as there are always many ways to solve a problem, this is not a concern at all. You need other ways to verify your work! $\endgroup$ – Raphael Nov 13 '16 at 9:25
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Nov 13 '16 at 18:40
  • $\begingroup$ @DavidRicherby Makes sense. Thanks! I'm mostly confused about the topic, so this question really is: is it true that the amortized cost of a given operation is bounded by $2n$ rather than $3n$ as the solutions manual shows? I felt like there are a number of things wrong with my solution, so I was hoping that some mistakes would be identified by experts. I do see that this question doesn't add real value to SE as a whole (the absence of a specific title hints at this). I'd be happy to change to the above mentioned question or delete this. $\endgroup$ – Readingtao Nov 13 '16 at 19:00
1
$\begingroup$

An amortized cost is just the average cost of a sequence of $n$ operations (in the worst cases). If I remember correctly, its definition is defined as

$$ \hat c(n) \sim \frac{\sum\limits_kc(k)}{n} $$

Now, $$ \hat c(n) = \begin{cases} 2n - 1 & \text{if $n$ is a power of 2} \\ 0 & \text{otherwise} \end{cases} $$ obviously fits that description. In the same vein, so does $$ \hat c(n)_{\text{alt}} = \begin{cases} n & \text{if $n$ is a power of 2} \\ 1 & \text{otherwise} \end{cases} $$ which is just our original cost function ;)

In fact, many such cost functions exist. However, none of them clearly spells out a tight bound on the cost of any arbitrary instruction.

For example, to say that $\hat c(n) \sim 2n$ is to say that the total cost of $n$ operations is approximately $\sum_k^n 2k = 1 \times n^2$. On the other hand, the true total cost of $n$ operations is \begin{align*} \sum_k c(k) &= n + (2^0 - 1) + (2^1 - 1) + \dots + (2^{\lfloor\log_2(n)\rfloor} - 1) \\ &= n + 2^{\lfloor \log_2(n) \rfloor + 1} - 1 - (\lfloor\log_2(n)\rfloor + 1) \\ &\le n + 2n - \log_2(n) - 2 \\ &\le 3n \end{align*}

This means that a good "amortization" technique here would give an amortized cost of $\hat c(n) = 3$ for any arbitrary $n$.

Now, why is $\hat c(n) = 3$ more "elucidating" than $\hat c(n) = \text{n is a power of 2} ~?~ 2n - 1 ~:~ 0$? Well, because it gives a uniform amortized value for every $n$. This then forms the (unspoken) cardinal rule of amortized runtime analysis:

Good amortized cost functions are not piecewise.

Why? If $\hat c(n) = \square$ uniformly, then we can easily say that each and every operation is bounded by the same $\square$.

Now, I can definitely hear some readers protest: "but I see case analyses in CLRS itself!" Do you? Well, for algorithms with multiple operations (say PUSH, POP, and MULTIPOP), then we need to give a cost function for each individual operation. However, the amortized cost function given for each operation is "continuous"!

Fret not, this is a pretty common problem. I haven't gone through CLRS myself, but I've stumbled upon these confusions as well when I first went through this technique.

We've already seen that $\hat c(n) = 3$ provides a valid bound, but it doesn't really give us any intuition about the problem (beyond pushing around some inequalities). Why 3? How do we get to that answer without working with (or around) arithmetic and geometric series?

There are good news and bad news. Bad news first: the most general framework you have here is the vague phrase that you already know; just figure out how much you have to pay upfront so you can cover the up to the next "big shock." While this might not seem like very much to work with, it does give us some general intuitions: the important aspect of the problem is not only the magnitude of these shocks (heh), but also their location.

In our case, we know that the location of these shocks are logarithmically distributed, which means that most of the time, you just incur a cost of one. However, these shocks are also pretty big, so you'll need to pay enough up-front to cover for them. In particular, after $2^k$ operations, you'll have to pay at least $2^k - 1$ operations and a further $2^k$ operations. This immediately suggests that $2^{k} + 2^{k} - 1 \le \hat c(2^k)$. Following a similar argument, we also have $\hat c(2^k) \le 2^{k} - k + k \times 2^k$. This refines our bound to $2n -1 \le \hat c(n) \le \lfloor \log_2 n + 1\rfloor n - \lfloor \log_2 n\rfloor$. After this, you can keep refining this bound until you get something as tight as possible. Unfortunately, there's really no way to do this unless you stumble onto the geometric series and realize that $\sum_k^n 2^k = 2^{n+1} - 1$, but at least this should give you a way to make gradual progress in your analysis.

Good luck!

$\endgroup$
  • $\begingroup$ Thank you so much! Lots of things to study on this page now, but I'm not complaining! Immensely grateful. $\endgroup$ – Readingtao Nov 13 '16 at 7:36
  • $\begingroup$ You use $\hat{c}$ inconsistently. $\endgroup$ – Raphael Nov 13 '16 at 9:26

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.