I am solving this problem from here.
The given relation is
$$T(n) = 2 T(\frac{n}{2}) + n^2, \, T(1) = 1$$
The solution via recurrence tree method is given as:
The zeroth level has a single node with cost $n^2$. The first level has two nodes, each with cost $(n/2)^2 = n^2/4$. The third level has four nodes, with cost $(n/4)^2 = n^2/16$.
In general, you can get the cost of a node by taking the subproblem size and squaring it. At the $i$th level, this cost is $n^2/4^i$. On the other hand, the $i$th level has $2^i$ nodes, so the total cost of each level is $n^2/2^i$.
The height of the tree is $\log n$.
Hence, summing the costs at each level we get
$$\sum_{n=0}^{\log n} \frac{n^2}{2^i} = n^2\sum_{n=0}^{\log n} \frac{1}{2^i} \leq 2n^2$$ by the sum of an infinite geometric series. Therefore the total cost of the algorithm is $\Theta(n^2)$.
As far as I understand, we use Big-Oh to give an upper bound i.e it cannot get worse than this and we use Theta to prove a tight bound i.e when we have proved a lower and an upper bound.
However, here we have only proved an upper bound, so shouldn't the answer be $O(n^2)$?
Is this a specific case when it doesn't matter if we interchange Big-Oh and Theta?
