in Algorithms retagged by
468 views
0 votes
0 votes

How is master theorem applicable here?

in Algorithms retagged by
468 views

2 Answers

4 votes
4 votes
Best answer

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})$.

selected by
0 votes
0 votes
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).