# Recurrence Equation upper limit problem

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?

• Your professor is wrong. Direct them to the proof of the master theorem. – Yuval Filmus Jul 29 '19 at 20:46
• @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? – MFranc Jul 29 '19 at 20:52
• @LucaGrignani The master theorem will render the same asymptotic bound as you have obtained, $\Theta(n^3)$. – John L. Jul 29 '19 at 21:05
• @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$. – ryan Jul 30 '19 at 0:39

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.