1
$\begingroup$

I was looking at my teacher's notes and came about the following recurrence equation :

$$ T(n) = \begin{cases} 1 &\quad\text{if } n\leq 1\\ 4T\left(\frac{n}{2}\right) + n^3 &\quad\text{if } n\gt1 \\ \end{cases} $$
In order to solve it I proceeded as follows :
$$ T(n) = n^3 + 4T\left(\frac{n}{2}\right) = n^3 + 4\big( 4T\left(\frac{n}{4}\right) + \left(\frac{n}{2}\right)^3 \big) = \\ n^3 + 4\left(\frac{n}{2}\right)^3 + 16T(\frac{n}{4}) = \cdots $$
I'll spare some latex and state that we can see from unwrapping the equation that at the generic level $i$ the incurred price is :
$$ T_i = 4^i\left(\frac{n}{2^i}\right)^3 $$
In order to compute the overall price we can sum all the prices incurred at all levels, obtaining :
$$ T(n) = \sum_{i=0}^{log^n -1}{\big(4^i\left(\frac{n}{2^i}\right)^3\big)} + 4^{log^n}T(1) = \\ n^3 \sum_{i=0}^{log^n-1}{\big(2^{2i}\frac{1}{2^{3i}}\big)} + n^2 = \\ n^3 \sum_{i=0}^{log^n-1}{\big(\frac{1}{2^{i}}\big)} + n^2 $$ My problem begins here. In order to solve it I'd say that the series in questions can be solved as :
$$ {\displaystyle \sum _{k=m}^{n}x^{k}={\frac {x^{m}-x^{n+1}}{1-x}}\quad {\text{with }}x\neq 1.} $$
which applied to my scenario would yield
$$ n^3 \left(\frac{1 - (\frac{1}{2})^{log^n}}{1 - \frac{1}{2}}\right) + n^2 = \\ 2n^3 - 2n^2 + n^2 = 2n^3 - n^2 = \Theta(n^3) $$
But my professor says :
$$ n^3 \sum_{i=0}^{log^n-1}{\big(\frac{1}{2^{i}}\big)} + n^2 \leq n^3 \sum_{i=0}^{\infty}{\big(\frac{1}{2^{i}}\big)} + n^2 = \\ n^3 \frac{1}{1 - \frac{1}{2}} + n^2 = 2n^3 + n^2 $$
And thus $T(n) = O(n^3)$ instead of $\Theta(n^3)$ since we proved only an upper limit.

My question is thus, why can't I solve the summation as I did instead of extending it to infinity?

$\endgroup$
  • $\begingroup$ Your professor is wrong. Direct them to the proof of the master theorem. $\endgroup$ – Yuval Filmus Jul 29 at 20:46
  • $\begingroup$ @YuvalFilmus well it's not technically wrong to say that it is $O(n^3)$ since the equation is correct. Yet I feel we can prove that it's $\Theta(n^3)$ as well. What would the master theorem suggest? $\endgroup$ – Luca Grignani Jul 29 at 20:52
  • $\begingroup$ @LucaGrignani The master theorem will render the same asymptotic bound as you have obtained, $\Theta(n^3)$. $\endgroup$ – Apass.Jack Jul 29 at 21:05
  • $\begingroup$ @LucaGrignani if you prove it is $O(n^3)$ then it's trivial to show it is $\Theta(n^3)$ because there is $n^3$ "work" done at the highest level of recurrence: $T(n) = 4T(n/2) + n^3 \geq n^3$. $\endgroup$ – ryan Jul 30 at 0:39
2
$\begingroup$

Yes, you could solve the summation in exact formula. Yes, you could obtain $T(n)=\Theta(n^3)$, a tighter asymptotic bound. Your professor would and should not forbid you to do that.

The message from your professor could be that an upper bound such as $O(n^3)$ is as good as $\Theta(n^3)$ more often than not. For example, once we know an algorithm runs in $O(n^3)$ time without a huge constant multiplier on a problem of input size $n$ less than 1000, then we can be comfortable starting implementing the algorithm, without worrying much that the code may take hours to run. A tighter asymptotic bound such as $\Theta(n^3)$ will not help us move ahead significantly further. On the other hand, such a tighter asymptotic usually comes with a heavier price, which is not much heavier in this particular problem, though.

$\endgroup$
  • $\begingroup$ By "price", I meant "computation". $\endgroup$ – Apass.Jack Jul 29 at 21:06
  • 1
    $\begingroup$ Thanks a lot, I was afraid I was missing something but didn't! $\endgroup$ – Luca Grignani Jul 29 at 21:10

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.