How to prove "Logarithms grow more slowly than polynomials" "Logarithms grow more slowly than polynomials. That is, Θ(lgn) grows more slowly than Θ(n^a) for any positive constant a." if y1= x^(1/2) and y2 = log (x) by comparing the graphs can say y1 > y2 But, is there a way to prove this?

drogaid1d8

drogaid1d8

Answered question

2022-11-17

How to prove "Logarithms grow more slowly than polynomials"
"Logarithms grow more slowly than polynomials. That is, Θ ( lg n ) grows more slowly than b ± b 2 4 a c 2 a for any positive constant a."
if y 1 = x 1 / 2 ) and y 2 = log ( x )
by comparing the graphs can say y 1 > y 2
But, is there a way to prove this?

Answer & Explanation

Jaydon Roth

Jaydon Roth

Beginner2022-11-18Added 13 answers

Actually, even more is true. For p > 0 and q > 0, we have that
lim x log p x x q = lim x ( log x x q / p ) p = ( lim x log x x q / p ) p = ( lim x 1 ( q / p ) x q / p ) p = 0
using continuity and l'Hôpital's rule.
Alice Chen

Alice Chen

Beginner2022-11-19Added 6 answers

May use
lim x 0 log ( 1 x ) 1 x = 0

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?