599 views
1 votes
1 votes

is the time complexity for this fuction is O(n)?

1 Answer

0 votes
0 votes
1 when T(n)=2T(n/2)+n

then a=2 ,b=2 ,k=1

then we apply the condition   a>b^k which give us a=b then T(n)=@(nlogn)     (@= theta_)

2.when T(n)=2T(n/2)+logn

then apply same method we get

T(n)=@(n) (@= theta)

Related questions

1 votes
1 votes
1 answer
1
2 votes
2 votes
1 answer
2
iarnav asked Jan 11, 2018
1,015 views
can we solve this T(n) = T(n/2) + 1 using master theorem?
3 votes
3 votes
0 answers
3
Sona Barman asked Jan 8, 2018
2,305 views
I have doubt regarding Master theorem.In which situation we should use Normal Master theorem/extended Master theorem?
1 votes
1 votes
1 answer
4
dragonball asked Dec 19, 2017
546 views
T(n) = 2T(n/2) + nlogna. O(nlogn)b.n(log^2n)c.O(n^2)