retagged by
505 views

2 Answers

4 votes
4 votes
T(n) = T(n/2) + 2

T(n/2) = T(n/4) + 2

T(n/4) = T(n/8) + 2

...

=> T(n) = T(n/2) + 2

= (T(n/4) + 2) + 2 = T(n/4) + 2*2

= (T(n/8) + 2) + 2*2 = T(n/8) + 2*3

= T(n/k) + 2*log k

 

Base condition: T(1) = 1

n/k = 1

=> k = n

Thus T(n) = T(n/n) + 2* log n

= 1 + 2 log n
edited by
0 votes
0 votes

The answer should be option A.

The tree will be log(n)+1 level deep. At each level you need constant time of 2 to merge them.So adding constant time 2 over log(n) level deep gives you 2(log(n)+1).

Related questions

1 votes
1 votes
1 answer
1
vivek_mishra asked Feb 17, 2019
937 views
Solve the recurrence relation given as: T(n)=2T(n-2)+n; where T(2)=2 and T(1)=0What is the solution?
1 votes
1 votes
1 answer
3
1 votes
1 votes
1 answer
4
sripo asked Feb 15, 2019
523 views
Let a and b be positive integers such that a b and a^ 2 − b^ 2 is a prime number.Then a^2 − b^ 2 is equal to(A) a − b(B) a + b(C) a × b(D) none of the above