When f(n) = n^.1 and g(n) = log(n)^10, does f(n) = Ω(g)?

Question

I was told that "any exponential trumps any logarithm".

But when the exponential is between zero and one, doesn't the execution time of the logarithm grow much faster? So by that logic it would be f = O(g)

I'm having trouble choosing whether to follow my intuition or what I've been told, but what I've been told may have been not totally accurate.

Answer 1

Let's try out some math here. One important fact is that the logarithm function is monotonically increasing, which means that if

log f(x) ≤ log g(x)

then

f(x) ≤ g(x)

Now, let's see what that does here. We have two functions, x^0.1 and log¹⁰ x. If we take their logs, we get

log (x^0.1) = 0.1 log x

and

log (log¹⁰ x) = 10 log log x

Since log log x grows much more slowly than log x, intuitively we can see that the function x^0.1 is going to eventually overtake log¹⁰ x.

Now, let's formalize this. We want to find some value of x such that

x^0.1 > log¹⁰ x

Let's suppose that these are base-10 logarithms just to make the math easier. If we assume that x = 10^k for some k, we get that

(10^k)^0.1 ≥ log¹⁰ 10^k

10^{0.1 k} > log¹⁰ 10^k

10^{0.1 k} > k

Now, take k = 100. Now we have that

10^{0.1 * 100} > 100

10¹⁰ > 100

which is clearly true. Since both functions are monotonically increasing, this means that for x ≥ 10¹⁰⁰, it is true that

x^0.1 > log¹⁰ x

Which means that it is not true that x^0.1 = O(log¹⁰ k).

Hope this helps!

Answer 2

The asymptotic analysis is really focused on the long run relationship (as n assumes larger values, how do the values of the functions compare)? It also disregards constants, which is why you sometimes see strange situations like f(x) = 10000000*x = O(x^2).

For large values of n, f(n) > g(n) which is all that really matters.

Answer 3

Another way to verify that n^0.1 = big omega(log^10(n)) by using the limit rule?

The limit rule is:

limit as n->infinity f(n)/g(g).

if the limit is positive infinity, f(n) != O(g(n)) & g(n) = O(f(n)) or f(n) = big omega(g(n))

if the limit is 0, f(n) = O(g(n)) & g(n) != O(f(n))

if the limit is a positive real number, f(n) = O(g(n)) & g(n) = O(f(n)) or f(n) = big theta(g(n))

For this problem:

let f(n) = O(n^0.1) and let g(n) = log^10(n)

That gives us the limit:

limit as n->infinity (n^0.1)/(log^10(n))

Using L'Hospital's rule on the limit 10 times we get:

limit as n->infinity ((0.1)^10 * ln^10(b) * n^0.1)/(10!) where b is the base of the log

Since the n term is only in the numerator, the limit approaches infinity.

By the limit rule

log^10(n) = O(n^0.1) & n^0.1 != O(log^10(n) or n^0.1 = big omega(log^10(n)).