Master Theorem Algorithm

Question

How is master theorem applicable here?

Answer 1

T(n)=2T(n/$\sqrt{2})$+n.

Here a=2(>=1) and b=1.414(>1).// it satisfies master theorem constraints.Now apply.

Basic logarithm formula $log_{b^{n}}^{a}$=$\frac{1}{n}log_{b}^{a}$

Check $n^{log_{b}^{a}}$ > f(n) or Less than f(n).

$n^{log_{$2^{1/2}$}^{2}}$ 

$n^{1/(1/2)log_{2}^{2}}$

$n^{2log_{2}^{2}}$

$n^{2}$ it is greater than n.

Hence TC=$O(n^{2})$.

Answer 2

First compute the value (n^(lag a base b)). that is (n^(log 2 base sqrt 2))=n^2. (Since (sqrt2)^2=2).now compare it with f(n)=n, so to apply master theorem,see first rule of master theorem. See we have to compare functions and whatever is greater we write in master theorem. To make function comparabe we write it in polynomial form like aT(n/b)=n^(log a base b).