Given a positive and increasing sequence $\{a_n\}$, what is the meaning of $a_n$ grows as for example $O(n\log n)$ or $O(n^2)$. I have read this in some books but the google search did not yield anything.
what is the meaning of $a_n$ grows as for example $O(n\log n)$ or $O(n^2)$
1
$\begingroup$
sequences-and-series
asymptotics
2 Answers
3
Actually this is the Big O or Landau-Notation which is explained here. In this example you can define a function
$f: \mathbb{N} \longrightarrow \mathbb{R}, f(n):=a_n$
and for example $a_n$ grows $O(n^2)$ now means that there are constants $k, n_0$ such that $\forall n>n_0 \; |f(n)| \leq |n^2\cdot k|$
-
0I am sorry you are right of course I was confused with tex :-) – 2011-06-11
3
Please see this Wikipedia article.