retagged by
497 views

2 Answers

Best answer
4 votes
4 votes

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

Related questions

1 votes
1 votes
1 answer
1
dragonball asked Oct 15, 2017
526 views
1 votes
1 votes
1 answer
2
1 votes
1 votes
1 answer
3
2 votes
2 votes
1 answer
4
iarnav asked Jan 11, 2018
1,130 views
can we solve this T(n) = T(n/2) + 1 using master theorem?