# Decide given complexity of given function

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?

• I don't quite get what your question is, but my guess is that you'd profit from looking at our reference questions. – Raphael Mar 5 '17 at 13:30
• 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. – D.W. Mar 5 '17 at 13:52
• Possible duplicate of Sorting functions by asymptotic growth – David Richerby Mar 5 '17 at 15:49

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.
• No, you cannot. The function $f$ grows strictly faster than $g$. – Yuval Filmus Mar 6 '17 at 10:05