Find Upper Bound for T(n)+T(n-1)+T(n/2)+n with recursive tree method.

sincsenekdq

sincsenekdq

Answered question

2022-09-07

Find Upper Bound for T ( n ) = T ( n 1 ) + T ( n 2 ) + n with recursive tree method.

Answer & Explanation

Phoenix Burch

Phoenix Burch

Beginner2022-09-08Added 11 answers

Step 1
A previous answer asserted correctly that T ( n ) 1 2 n 2 and wrongly that the property T ( n ) c n 2 is hereditary (that is, if it holds for every k n 1 it holds for n) for every c 2 .
In fact, the property T ( n ) c n 2 is not hereditary and the complexity is neither polynomial nor exponential. It seems that log T ( n ) ( log n ) 2 / ( 2 log 2 ) and one can probably check that, for every positive ε , the property
exp ( ( log n ) 2 ε ) T ( n ) exp ( ( log n ) 2 + ε )
is hereditary for every n large enough.

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?