1
$\begingroup$

I'm trying to determine correct notation for the given functions which are $f(n) = n$ and $g(n) = (log(n))^{100}$. Moreover, I don't understand while calculating its complexity using limit because calculator shows that it goes infinity, so f(n) is growing faster than g(n). But, I found vice versa. Could you explain me where I'm doing wrong? enter image description here

$\endgroup$
  • 1
    $\begingroup$ I don't quite get what your question is, but my guess is that you'd profit from looking at our reference questions. $\endgroup$ – Raphael Mar 5 '17 at 13:30
  • 1
    $\begingroup$ What do you mean by "determine correct notation for a function"? Also, don't use images as main content of your post. This makes your question harder to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. Note that you can use LaTeX. $\endgroup$ – D.W. Mar 5 '17 at 13:52
  • 2
    $\begingroup$ Possible duplicate of Sorting functions by asymptotic growth $\endgroup$ – David Richerby Mar 5 '17 at 15:49
1
$\begingroup$

This answer assumes that $\log$ is to the base 2.

Consider $n = 2^{1000}$. Then $$ f(n) = 2^{1000}, \quad g(n) = (\log_2 2^{1000})^{100} = (1000)^{100} < (1024)^{100} = (2^{10})^{100} = 2^{1000}. $$ If you increase $n$ even more, you will see an even more dramatic difference between $f(n)$ and $g(n)$. You just have to consider large enough $n$, perhaps too large for your calculator.

What this example shows that even though $f(n)$ grows faster than $g(n)$, for values of $n$ encountered in practice the situation is very different, with $g(n)$ being much larger than $f(n)$. This shows the limits of asymptotic analysis – it is a natural and useful mathematical notion, but it isn't always a good model for reality.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your approach. We can find a constant and n0 to prove its omega, which is your approach; however, we can find a constant(1) and n0(4) to prove bigo as well. Can't we? So, shouldn't it be theta as a result? $\endgroup$ – snr Mar 6 '17 at 8:05
  • $\begingroup$ No, you cannot. The function $f$ grows strictly faster than $g$. $\endgroup$ – Yuval Filmus Mar 6 '17 at 10:05

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.