4
$\begingroup$

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!

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\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 '13 at 5:04
  • 2
    $\begingroup$ Why does $log(n)=O(n^{0.000001})$? Usually $log(n) = O(log(n))$ $\endgroup$ – chrishiestand Oct 7 '13 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$ – Gilles 'SO- stop being evil' Oct 7 '13 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$ – chrishiestand Oct 7 '13 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$ – Gilles 'SO- stop being evil' Oct 7 '13 at 8:46
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ While true, this is unrelated to the question at hand. Which is about $n^{.9999} \log n$, not $n \log n$. $\endgroup$ – 6005 May 16 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$ – Adwait Mathkari Jun 16 at 12:37
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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