Asymptotic complexity of power of logs I'm trying to simplify Theta(lg^k(n/2))

Aliyah Thompson

Aliyah Thompson

Answered question

2022-11-03

Asymptotic complexity of power of logs
I'm trying to simplify Θ ( l g k ( n / 2 ) ).
I believe it's Θ ( l g k n ) but i don't know if the following proof is correct... i'd love to receive some input
I tried doing -
Θ ( l g k ( n / 2 ) ) = Θ ( l g ( n / 2 ) l g ( n / 2 ) l g ( n / 2 ) . . . l g ( n / 2 ) ) = Θ ( ( l g n l g 2 ) ( l g n l g 2 ) ( l g n l g 2 ) . . . ( l g n l g 2 ) ) = Θ ( Θ ( l g n ) k ) = Θ ( l g k n )

Answer & Explanation

Ryan Davies

Ryan Davies

Beginner2022-11-04Added 18 answers

The upper O-bound is trivial.
To establish the lower bound,
consider the following limit and apply L Hospital rule repeatedly
lim x lg k 2 x lg k x
Note that
d d x ( lg 2 x ) = d d x ( lg x )

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?