Register

#Made Easy Test Series

936 views
0 0 votes

Find the time complexity of the given program

1 Answer

0 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
Voting & Accepting an answer helps improve the community
← Previous · Applied Live TestNext → · Self doubts
← Previous in category · Radix Sort--Algorith...Next in category → · Self doubts
Position:
Show:

Related questions

1 1 vote
1 answers 1 answer
1.3k
1.3k views
Hira Thakur asked Aug 14, 2016
1,331 views
#made easy
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)
1 1 vote
1 answers 1 answer
584
584 views
Hira Thakur asked Aug 14, 2016
584 views
#made easy
soluation for the recurrence relation isf(x)=2T(floor(rootn))+logn1.O(nlogloglogn)2.O(nloglogn)3.O(loglogn)4O(lognloglogn)
0 0 votes
1 1 answer
1.0k
1.0k views
gutsyParth asked Jul 14, 2024
1,040 views
#made-easy-test-series
Total number of 2 x 1 multiplexers required to implement full subtractor is1. five 2 x 1 multiplexers with available of NOT gates2. seven 2 x 1 multiplexers with availabl...
0 0 votes
0 0 answers
1.1k
1.1k views
jay03 asked Nov 28, 2022
1,103 views
#CompilerDesign #made-easy-test-series
what should be the ans??according to me answer should be 7 nodes, 8 edges but 5 nodes, 6 edges is given in the answer key!please tell me what am i doing wrong.