Bounding a logarithmic relation If I have the following relation T(n)<=an⌈lg(n)⌉−an+2bn+n, is it possible to bound T(n) such that it is in the form T(n)<=an lg(n)+bn for some constants a,b>=0?

samuelaplc

samuelaplc

Answered question

2022-10-09

Bounding a logarithmic relation
If I have the following relation T ( n ) a n lg ( n ) a n + 2 b n + n, is it possible to bound T ( n ) such that it is in the form T ( n ) a n lg ( n ) + b n for some constants a , b 0?

Answer & Explanation

vakleraarrc

vakleraarrc

Beginner2022-10-10Added 6 answers

Note:
a n log ( n ) a n + 2 b n + n a n log ( n ) ) a n + 2 b n + n = a n log ( n ) + ( 2 b a + 1 ) n
The RHS is greater than the required expression so long as 2 b a + 1 > b, so it is not necessarily possible.

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?