FORMAL NOTATION FOR TIME AND SPACE


An Upper Bound

$$T(n) ~=~ O(f(n)) ~~{\rm when}~~ (\exists c \gt, n_0\geq0) (\forall n \gt n_0)(T(n) ~\leq ~ cf(n))$$

Lower Bound

$$T(n) ~=~ \Omega(f(n)) ~~{\rm when}~~ (\exists c \gt, n_0\geq0) (\forall n \gt n_0)(T(n) ~\geq ~ cf(n))$$

A Tight Bound

$$T(n) ~=~ \Theta(f(n)) ~~{\rm when}~~ T(n) = O(f(n)) ~~{\rm and}~~ T(n) = \Omega(f(n))$$

 
 
Examples

1.

3n²  =  O(n²)

2.

$3n^2 ~=~ \Omega(n^2)$

3.

$3n^2 ~=~ \Theta(n^2)$

4.

$3n^2 ~\neq~ O(n\lg n)$

5.

3n²  =  O(n³)

6.

$3n^2 ~\neq~ \Omega(n^3)$

7.

$\lg n ~=~ O(n^{0.1})$