Apply Master theorem to show T(n)=2T(n/2)+n^2 is theta(n^2)

Introduction : In this question, we will apply master theorem to show T(n)=2T(n/2)+n^2 is theta(n^2). Master theorem finds an upper bound for some recurrence relations if some conditions on parameters are satisfied.

Question : Apply Master theorem to show

\[T(n)=2T\left(\frac{n}{2}\right)+n^{2}\]

is θ(n^2 )

Solution:

Given recurrence relation

\[T(n)=2T\left(\frac{n}{2}\right)+n^{2}\]

Comparing it from the standard form of Master theorem

\[T(n)=aT\left(\frac{n}{b}\right)+n^{c}\]

we get a=2, b=2, c=2

The condition of the master theorem that a, b, c satisfies is

\[a<b^c \]

because \[2<2^2\]

So by master theorem

T(n)=θ(n^c )= θ(n^2 ).