I need to find the upper asymptotic bound for the recursion: T(k)=2T(k-1)+1/k; I was able to determine: (1) The height of this tree is k-1; (2) The cost of each level is (2i)/(k-i)

jatericrimson8b

jatericrimson8b

Answered question

2022-09-04

Step 1
I need to find the upper asymptotic bound for the recursion:
T ( k ) = 2 T ( k 1 ) + 1 k
I was able to determine:
1) The height of this tree is k 1
2) The cost of each level is 2 i k i

Answer & Explanation

Ashlee Ramos

Ashlee Ramos

Beginner2022-09-05Added 20 answers

Step 1
I tried to solve this from scratch:
T ( n ) = 2 T ( n 1 ) + 1 n T ( n ) = 2 ( 2 T ( n 2 ) + 1 n 1 ) + 1 n T ( n ) = 2 ( 2 ( 2 T ( n 3 ) + 1 n 2 ) + 1 n 1 ) + 1 n = 2 3 T ( n 3 ) + 2 2 n 2 + 2 1 n 1 + 2 0 n T ( n ) = 2 k T ( n k ) + i = 0 k 1 2 i n i When  n k = 0 (instead of n - k = 1, to simplify) k = n T ( n ) = 2 n T ( 0 ) + i = 0 n 1 2 i n i T ( n ) = 2 n 1 2 n + 1   2 F 1 ( 1 , n + 1 ; n + 2 ; 1 2 ) n + 1 1 2 log ( 1 2 )
With a helpful answer here and here.
Intuitively, however, I think that (proof here):
2 F 1 ( 1 , n + 1 ; n + 2 ; 1 2 )     O ( 2 n ) .

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?