# what is the meaning of $a_n$ grows as for example $O(n\log n)$ or $O(n^2)$

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.

-

## 2 Answers

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|$$

-
I would have said: $|f(n)| \le k\;n^2$. – GEdgar Jun 11 '11 at 16:54
I am sorry you are right of course I was confused with tex :-) – Listing Jun 11 '11 at 16:59