What is the sum of recursive logarithms?I am trying to deduce the complex of a rather odd algorithm

Sariah Mcguire

Sariah Mcguire

Answered question

2022-10-16

What is the sum of recursive logarithms?
I am trying to deduce the complexity of a rather odd algorithm. I have got it down to this form:
O ( n × ( n ) 2 + n × ( lg n ) 2 + n × ( lg lg n ) 2 +   . . . +   n × a 2 )
= O ( n 2 + n × ( lg n ) 2 + n × ( lg lg n ) 2 +   . . . +   n × a 2 )
Where a is a constant value.
I have a hunch that in the limit to infinity n 2 dominates. However I do not know how to prove this. Is there a closed form for the sum of recursive logarithms, such as I have in the above formula?

Answer & Explanation

Pradellalo

Pradellalo

Beginner2022-10-17Added 16 answers

You are right. n 2 dominates. It is because log ( n ) is asymptotically lower than n and n is asymptotically lower than n 2 . This is very easy to prove. If your book/class allows you to assume this then just state it and you're done. If this assumption is not allowed(well it should be) you can prove by showing that,
d ( log ( x ) ) d x < d x d x < d ( x 2 ) d x
for sufficiently large 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?