with Substitution induction hypothesis Let Qn 4Qn2 Thetan

with Substitution / induction hypothesis.

Let Q(n) = 4Q(n/2) + Theta(n). Prove that Q(n) = O(n^2).

Solution

Answer:

Proof : -

q(n)=O(n^2)

therefore , 4q(n/2)=4*O(n^2/4)

O(4*n^2/4)=O(n^2)

and O(n^2)+theta(n)= O(n^2)