411 views
0 votes
0 votes

T(n) = T(n/2)+2​​​​​n find the complexity? 

A) O(n log n)

B)O(n2)

C)O(2n)

D) O(n)

1 Answer

0 votes
0 votes

by applying master theorem 

if n^logb(a) is >f(n) then tc=o(n^logb(a))

else n^logb(a)==f(n) then tc=o(n^logb(a)logn)

else o(f(n))

coming to given problem

n^log2(1)<2^n

then TC=O(2^n)

Related questions

0 votes
0 votes
1 answer
1
anup9544 asked Oct 26, 2016
248 views
Solve the recurrence equation T(n)= 2 T(n/2) + (n-1); n>1 =1 ; n=1T(n)=?A) n+1B) 2n-1C) 1+nlogn D) none
0 votes
0 votes
1 answer
2
anup9544 asked Oct 26, 2016
291 views
Which choice gives the θ notation for the amount of time used by the code segment belowFor (i=n/2 ; i<=n ; i++)For (j=1; j<= n; j+=n/2)For (k=1; k<=n; k*=2)X=x+1;A)θ(nl...