Register

#Made Easy Test Series

501 views
0 votes
0 votes

Find the time complexity of the given program

User Avatar

1 Answer

0 votes
0 votes
T(n) = T(n-1) + T ( n-2 ) + T( n/2 ) + C
 

T(n- 1 ) > T ( n-2 )   &&  T ( n -1 ) >  T ( n/2 )
 

IF WE IGNORE THE T ( n /2  )
so
T( n ) =  2 T ( n-1 ) + c  
from master method
T ( n ) = a T ( n-b ) + n^k

a>1   than solution = O ( n^k a^n/b  )
 here  a= 2   &  k= 0

so    complexity =  0 ( n^0 2^n/1 ) =   0 ( 2^n )

IF WE NOT IGNORE THE T( n /2 )
T ( n) = 3T ( n-1 ) +c
solution for is
a= 3  k = 0
complexity =  O ( n^k  3^n/1 ) = 0 ( 3^n )  

now my dout is we have to ignore the T ( n/2 ) or not …...thanks
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
Hira Thakur asked Aug 14, 2016
981 views
#made easy
Big oh estimate for f(x)=(x+1)log($x^2 +1$)+3$x^2$ is given as 1.O(xlogx) 2.O($x^2$) 3.O($x^3$) 4O($x^2$logx)
Big oh estimate forf(x)=(x+1)log($x^2 +1$)+3$x^2$ is given as1.O(xlogx)2.O($x^2$)3.O($x^3$)4O($x^2$logx)
User Avatar
1 votes
1 votes
1 answer
2
Hira Thakur asked Aug 14, 2016
335 views
#made easy
soluation for the recurrence relation is f(x)=2T(floor(rootn))+logn 1.O(nlogloglogn) 2.O(nloglogn) 3.O(loglogn) 4O(lognloglogn)
soluation for the recurrence relation isf(x)=2T(floor(rootn))+logn1.O(nlogloglogn)2.O(nloglogn)3.O(loglogn)4O(lognloglogn)
User Avatar
Link Copied!