Find the tight upper and lower bounds for the following recurrence: T(n) = 2T(n/2) + 6T(n/3) + n^2, if n >= 3 = 1 if n <= 2

moidu13x8

moidu13x8

Answered question

2022-09-07

Find the tight upper and lower bounds for the following recurrence:
T ( n ) = 2 T ( n 2 ) + 6 t ( n 3 ) + n 2 ,   if   n 3 = 1   if   n 2

Answer & Explanation

acilschoincg8

acilschoincg8

Beginner2022-09-08Added 12 answers

Step 1
I think your Level 3 is wrong: it should derive from the Level 2 terms 2 T ( n 2 ) and 6 T ( n 3 ) , not T ( n 2 ) and T ( n 3 ) . So, combining the terms within each level, we have:
Level  1 : n 2 Level  2 : ( 7 6 ) n 2 Level  3 : ( 7 6 ) 2 n 2 Level  k : ( 7 6 ) k 1 n 2
A lower bound is found via the "shortest path" through the levels from n to 1:
n , n ( 1 3 ) , n ( 1 3 ) 2 , n ( 1 3 ) 3 , , 1 = n ( 1 3 ) log 3 n .
This gives a lower asymptotic bound:
T ( n ) n 2 ( 1 + ( 7 6 ) + ( 7 6 ) 2 + + ( 7 6 ) log 3 n ) = n 2 ( 7 / 6 ) 1 + log 3 n 1 ( 7 / 6 ) 1 = 7 n 2 ( 7 / 6 ) log 3 n 6 n 2 = 7 n 2 + log 3 ( 7 / 6 ) 6 n 2 using  x log a y = y log a x T ( n ) = Ω ( n 2 + log 3 ( 7 / 6 ) ) since  log 3 ( 7 / 6 ) > 0 .
An upper bound is found via the "longest path" through the levels from n to 2 (not to 1 since the relation is valid for n 3 ):
n , n ( 1 2 ) , n ( 1 2 ) 2 , n ( 1 2 ) 3 , , 2 = n ( 1 2 ) log 2 n 1 .
These two bounds can be verified inductively: for some constant c,
T ( n ) 2 c ( n 2 ) 2 + log 3 ( 7 / 6 ) + 6 c ( n 3 ) 2 + log 3 ( 7 / 6 ) = c n 2 + log 3 ( 7 / 6 ) [ 1 2 2 log 3 ( 6 / 7 ) + 4 7 ] c n 2 + log 3 ( 7 / 6 ) since  [ 1 2 2 log 3 ( 6 / 7 ) + 4 7 ] 1.025 and: T ( n ) 2 c ( n 2 ) 2 + log 2 ( 7 / 6 ) + 6 c ( n 3 ) 2 + log 2 ( 7 / 6 ) + n 2 = n 2 + log 2 ( 7 / 6 ) [ c ( 3 7 + 2 3 3 log 2 ( 6 / 7 ) ) + n log 2 ( 6 / 7 ) ] c n 2 + log 2 ( 7 / 6 ) for  c ( 3 7 + 2 3 3 log 2 ( 6 / 7 ) ) + n log 2 ( 6 / 7 ) c 0.95 c + 1 n 0.22 c c 20 n 0.22 so  c = 20  is sufficient.

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?