Recurrence Equation upper limit problem

Question

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?

Answer 1

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.