# Exercise C-1.3 in Algorithm design and applications

There is a exercise in Algorithm design and applications (Goodrich) that I don't understand. It says:

What is the amortized running time of the operations in a sequence of n operations $$P=p_1p_2 \cdots p_n$$ if the running time of $$p_i$$ is $$\Theta(i)$$ if i is a multiple of 3, and a constant otherwise.

I've read upon amortization and the accounting method. But I don't understand what $$\Theta(i)$$ is, because for $$p_3$$ it is $$\Theta(3)$$, but isn't that also in constant time?

I'm suppose that the task is to sum the running time of each operation up, and possibly divide by the number of operations. In order to find the amortized running time.

That statement means that there exist constants $$c_\ell,c_u$$ and $$n_0$$ such that if $$i \ge n_0$$, then $$c_\ell i \le p_i \le c_u i$$.
As a warmup, try solving the problem if $$p_i=i$$. If you can solve it for that case, the rest is just bookkeeping details.
• This is my attempt: if $p_i=i$, then we have to "spend" (on multiples of 3) $\sum_{i=1}^{\lfloor \frac{n}{3} \rfloor}(3i) = 3\frac{\frac{n}{3}(\frac{n}{3}+1)}{2}$. We have to "charge" the same amount on the rest. So it takes $\frac{3}{2} (\frac{n^2}{9}+\frac{n}{3})$ with is $n^2$ time... Commented Jun 5 at 3:02