1
$\begingroup$

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 2

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

  • 0
    I am sorry you are right of course I was confused with tex :-)2011-06-11
3

Please see this Wikipedia article.