This is more of a computer science question but it uses calculus and proof techniques so I think it might be more appropriate here. Basically, how do I prove that, for any constant K>=1, that log^K(N)=O(N) Where O denotes the Big O.I am thinking of proving this by induction but not sure what the base case should. In addition to this, I think L'Hopital's rule can be used here with the two functions. Can anyone give me a solid hint on how to start this ? Many thanks !

Asher Kaufman

Asher Kaufman

Open question

2022-08-31

Any power of logarithm is O ( N )
This is more of a computer science question but it uses calculus and proof techniques so I think it might be more appropriate here. Basically, how do I prove that,
for any constant K 1, that log K ( N ) = O ( N )
Where O denotes the Big O.I am thinking of proving this by induction but not sure what the base case should. In addition to this, I think L'Hopital's rule can be used here with the two functions. Can anyone give me a solid hint on how to start this ? Many thanks !

Answer & Explanation

Paola Mercer

Paola Mercer

Beginner2022-09-01Added 11 answers

Hint:
Consider lim n ( log n ) k n = lim n k ( log n ) k 1 n = lim n k ( k 1 ) ( log n ) k 2 n = = ?
By using L'Hospital's rule k times, and assuming k is an integer. If k is not an integer, then use same for ( log n ) k

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?