1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.