retagged by
391 views
0 votes
0 votes
T(n)=2T(n/2)+n  ;  n>1

         =1                ; . n=1

What is the time complexity and how??
retagged by

1 Answer

1 votes
1 votes

T(n) = 2T($\frac{n}{2}$)+n  ;  n>1
       = 1                ; . n=1

put $\frac{n}{2}$ in place of n ===> T( $\frac{n}{2}$ ) = 2 T($\frac{n}{4}$) + $\frac{n}{2}$  ===> T( $\frac{n}{2}$ ) = 2 T($\frac{n}{2^{2}}$) + $\frac{n}{2}$ ---- (1)

SUBSTITUTE (1) in the original equation

T(n) = 2 ( 2 T($\frac{n}{2^{2}}$) + $\frac{n}{2}$ ) + n

T(n) = 22 T($\frac{n}{2^{2}}$) + 2 . $\frac{n}{2}$  + n

T(n) = 22 T($\frac{n}{2^{2}}$) + n + n =  22 T($\frac{n}{2^{2}}$) + 2 n 

T(n) =  23 T($\frac{n}{2^{3}}$) + 3 n

........

T(n) =  2k T($\frac{n}{2^{k}}$) + k n ------------- (2)

for matching base condition T($\frac{n}{2^{k}}$) = T(1)

 $\frac{n}{2^{k}}$ = 1 ====> n= 2k ====> k = log2 n  -----> substitute this in (2)

T(n) =  n T( 1 ) + ( log2 n ) n = n + n  log2 n  =O (  n log2 n )

Related questions

1 votes
1 votes
0 answers
1
syncronizing asked Mar 15, 2019
1,253 views
Is this the correct way to solve ?Q) int algorithm(int n){ int sum =0;k,j; for (k=0;k<n/2;k++) for(j=0;j<10;j++) sum++; return 4*algorithm(n/2)*algorit...
1 votes
1 votes
1 answer
2
VikramRB asked Jan 20, 2019
1,005 views
What is the time complexity of the following recurrence relation and step to derive the same$T(n) = T(\sqrt{n}) + log(logn)$
0 votes
0 votes
0 answers
4
garvit_vijai asked Nov 17, 2018
449 views
How to solve the following recurrence relation?T(n) = T(n-6) + n2 , n>7T(n) = 1 , n<= 7