# Big O Notation of $n^{0.999999}\log(n)$

I'm taking the MIT Open Courseware for Introduction to Algorithms and I'm having trouble understanding the first homework problem/solution.

We are supposed to compare the asymptotic complexity (big-O) for different functions:

$f_1(n) = n^{0.999999}\log(n)$
$f_2(n) = 10000000n$

$f_2(n)$ is obviously O(n), but the big-O given for $f_1(n)$ confuses me and I don't follow the given solution.

The solution says $f_1(n)$ has less Big-O complexity than $f_2(n)$:

"recall that for any $c > 0$, $log(n)$ is $O(n^c)$.

Therefore we have: $f(n) = n^{0.999999}log(n) = O(n^{0.999999}n^{0.000001}) = O(n) = O(f_2(n))$"

I do not understand the logic underlying the solution. I may be forgetting something simple? Can someone break it down for me? Thanks!

• Take c = 0.000 000 001 instead of c = 0.000 001. – gnasher729 May 16 '20 at 21:38

If $g = O(g')$ and $h$ is nonnegative then $h \cdot g = O(h \cdot g')$ — in English, if $g$ grows slower than $g'$ then multiplying by a positive function doesn't affect that fact. (If you aren't sure about this, do the proof with quantifiers).

Since $\log(n) = O(n^{0.000001})$, $n^{0.999999} \cdot \log(n) = O(n^{0.999999} \cdot n^{0.000001})$. Since $n^{0.999999} \cdot n^{0.000001} = n$, we have $f_1(n) = O(n)$.

While it is true that $f_2(n) = O(n)$, this is not relevant here. What you need is $n = O(f_2(n))$, which is also true.

Intuitively, a higher exponent trumps a logarithm. A multiplicative constant is not significant.

• +1 for this explanation. If $f_1(n) = n\log(n)$ , then it would have been bigger than $f_2(n)$ right ? – avi Oct 7 '13 at 5:04
• Why does $log(n)=O(n^{0.000001})$? Usually $log(n) = O(log(n))$ – chrishiestand Oct 7 '13 at 7:52
• @chrishiestand In spite of the confusing notation, $f = O(g)$ isn't anything like an equality. It's rather an order relation (technically, it's a preorder). Some people write $O \in O(g)$, which is more mathematically precise but less traditional. $f = O(g)$ means that $f$ is less than $g$, asymptotically, up to a scaling factor. $n^{0.000001}$ is an upper bound for $\log(n)$, less tight than $\log(n)$ is. – Gilles 'SO- stop being evil' Oct 7 '13 at 8:01
• Gilles, thanks for taking the time to answer me. I feel like I understand what you're saying conceptually about big-O, but I still don't understand where .000001 comes from precisely. Sorry, I'm feeling pretty dense at the moment. – chrishiestand Oct 7 '13 at 8:10
• @chrishiestand $0.000001$ comes from trying to match $n^{0.999999}$ with $n$: $f_2(n)/f_1(n) = 10000000 n / (n^{0.999999} \log(n)) = 10000000 n^{0.000001} / \log(n)$. By the way, if you want to compare two positive functions and you have no a priori idea how to do it, this is a valid approach: calculate $f_1/f_2$, and see if it's $O(1)$ (so $f_1 = O(f_2)$) or $\Omega(1)$ (so $f_1 = \Omega(f_2)$). – Gilles 'SO- stop being evil' Oct 7 '13 at 8:46

If we consider really large numbers like $$10^{1000}$$ then $$n\log n$$ will be equal to

$$n\log 10^{1000} = 1000n\log 10 = 2302n < 1000000n.$$

Thus even for really really big $$n$$s, $$n\log n<1000000n$$.

This I guess is a layman logic, and theoretically, infinite $$n$$ should give $$n\log n>10000000n$$. But not really.

• While true, this is unrelated to the question at hand. Which is about $n^{.9999} \log n$, not $n \log n$. – 6005 May 16 '20 at 0:23
• For n = 10**100 the value of ( n - n**0.9999) / n = .022 so i think probably n**0.9999 ~ n. (Although not sure as it depends on the accuracy needed and the size of the no.) – Adwait Mathkari Jun 16 '20 at 12:37

Just use the definition, i.e., check if $$\lim_{n \to \infty} f_1(n) / f_2(n) < \infty$$. Computing this, you'll see that $$0 < \infty$$ and you are done.