# Big-Oh vs Theta in recurrence tree method

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?

In this particular case $$T(n) = 2T(n/2) + n^2 \geq n^2$$, so the lower bound is trivial.