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!

  • $\begingroup$ Take c = 0.000 000 001 instead of c = 0.000 001. $\endgroup$
    – gnasher729
    May 16, 2020 at 21:38

3 Answers 3


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.

  • $\begingroup$ +1 for this explanation. If $f_1(n) = n\log(n)$ , then it would have been bigger than $f_2(n)$ right ? $\endgroup$
    – avi
    Oct 7, 2013 at 5:04
  • 2
    $\begingroup$ Why does $log(n)=O(n^{0.000001})$? Usually $log(n) = O(log(n))$ $\endgroup$ Oct 7, 2013 at 7:52
  • 2
    $\begingroup$ @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. $\endgroup$ Oct 7, 2013 at 8:01
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 7, 2013 at 8:10
  • 2
    $\begingroup$ @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)$). $\endgroup$ Oct 7, 2013 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.

  • $\begingroup$ While true, this is unrelated to the question at hand. Which is about $n^{.9999} \log n$, not $n \log n$. $\endgroup$ May 16, 2020 at 0:23
  • $\begingroup$ 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.) $\endgroup$ Jun 16, 2020 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.