If you have a function, $f(n)$ such that $$\lim_{n\rightarrow\infty}\frac{f(n)}{n}=\infty$$ what can you conclude about $f(n)$? Must you necessarily have $f(n)=n^x$ for some $x>1$?
Asked
Active
Viewed 89 times
2
-
3$f(n) = n^2 + 1$, $f(n) = e^n$, $f(n) = n^2 + e^n + \cos n + \sin n$, .... – Jan 29 '14 at 17:26
4 Answers
3
By definition: this limit means
$$\forall A>0\;\exists B>0\quad |\quad \forall n\ge B\; f(n)\ge A\times n$$ but notice that $f(n)$ may be less that $n^x,\, x>1$ (at least asymptoticaly) and $f(n)=n\log n$ is one example.
0
No, you will find a lot of counter-examples (like $f(n)=n!$), but hence $\frac{f(n)} n $ is supposed to grow to infinity you know that $$f\in\Omega(n^x)$$ for suitable $x\geq1$
user127.0.0.1
- 7,267
0
In big $O$ notation, it means that $f\notin O(n)$ where $O(h(n)) = \{g:(0,\infty)\to \mathbb{R}\;|\; \exists c>0. \exists x_0\in (0,\infty).\forall x\geq x_0. |g(x)|<c|h(x)|\}$.
Antoine
- 3,439
0
As pointed in the other answers, $f(n)$ could be much much larger than $n$.
But that is not always the case. For example, you cannot even conclude that $f(n)>n^x$ for some $x >1$. $f(n)=n \ln(n)$ is an example for this.
N. S.
- 132,525