recurrence relation involving big O notation

Question

The solution of the recurrence relation T(n) = 2T(n/2) + O(n^2) is given as Big theta of n^2.

How do we get this solution.

The way I solved it :- the height of the recurrence tree is logn. And we have at each step n^2 complexity. SO recurrence relation is O(n^2 logn).

How do we get answer in Big theta in this case?

Answer 1

You can refer to "Master Theorem".

Your problem falls into Case 3 of the theorem, so according to its conclusion, the complexity is Θ(n^2).