Register

Please help me solve this Recurrence Relation

876 views
1 1 vote

*****NOTE: I'm not looking to find the Time Complexity, but I'm looking for number of comparisons and the answer is

3/2n -2

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

T(2) = 1

T(1) = 0

and I'm stuck at this point - 

T(n)= 2k T(n/2k) + 2k+2k-1+ . . . +2

and I found out k = log n-1, but stuck at solving for k.

1 Answer

Voting & Accepting an answer helps improve the community
← Previous · self doubtNext → · Doubt
← Previous in category · Gradeup Test seriesNext in category → · Doubt
Position:
Show:

Related questions

1 1 vote
1 1 answer
982
982 views
kallu singh asked Aug 13, 2017
982 views
Please Solve this Recurrence Relation
Q. In Quick sort ,for sorting n element ,the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case tome complexity of the Qu...
1 1 vote
1 1 answer
1.2k
1.2k views
LavTheRawkstar asked Feb 1, 2017
1,194 views
Solve the following Recurrence using any method just help in solving
T(n) = T(n-1) + n
2 2 votes
2 2 answers
2.0k
2.0k views
LavTheRawkstar asked Jan 31, 2017
2,020 views
Using Recurrence Tree method solve for the following Recurrence Relation
T(n)= 3$T(\frac{n}{4})$ + θ(n2)
3 3 votes
1 1 answer
4.3k
4.3k views
dd asked Aug 11, 2016
4,338 views
time complexity to solve recurrence relation
recurrence relation for the functional value of F(n) is given below :$F(n) = a_{1}F(n-1) + a_{2}F(n-2) + a_{3}F(n-3) + \ldots + a_{k}F(n-k)$ where $a_{i} =$ non zero con...