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$
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.

$\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
  • 1
    $\begingroup$ Why does $log(n)=O(n^{0.000001})$? Usually $log(n) = O(log(n))$ $\endgroup$ – chrishiestand Oct 7 '13 at 7:52
  • 1
    $\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

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.