1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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... $\endgroup$
    – GeekGuy
    Commented Jun 5 at 3:02
  • $\begingroup$ @ScienceGuy, I'm afraid that verifying your attempt is not part of this site's purpose, but I'm glad you found the answer to your question helpful! $\endgroup$
    – D.W. ♦
    Commented Jun 5 at 4:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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