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?
$\begingroup$
$\endgroup$
3
asked Mar 5, 2017 at 13:12
Soner from The Ottoman EmpireSoner from The Ottoman Empire
1151 gold badge1 silver badge6 bronze badges
-
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$– RaphaelCommented Mar 5, 2017 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. ♦Commented Mar 5, 2017 at 13:52
-
2$\begingroup$ Possible duplicate of Sorting functions by asymptotic growth $\endgroup$– David RicherbyCommented Mar 5, 2017 at 15:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Mar 5, 2017 at 15:31
-
$\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$ Commented Mar 6, 2017 at 8:05
-
$\begingroup$ No, you cannot. The function $f$ grows strictly faster than $g$. $\endgroup$ Commented Mar 6, 2017 at 10:05