Asymptotic Notations

There are 3 main asymptotic notations to denote time complexity:

  • Big-O (O)
  • Big-Omega (Ω\Omega)
  • Big-Theta (Θ\Theta)

We also have little-o (o) and little-omega (ω\omega)

Big-O (O)

Big-O is the most commonly used notation. It denotes the worst-case time complexity.

We say f(n) = O(g(n)) iff there exists some constant c>0, and n0n_0 such that f(n) <= c.g(n) for all n >= n0n_0

g(n) will be the upper-bound for f(n).

Big-Omega (Ω\Omega)

We say f(n) = Ω\Omega(g(n)) iff there exists some constant c>0, and n0n_0 such that f(n) >= c.g(n) for all n >= n0n_0

g(n) will be the lower-bound for f(n).

Big-Theta (Θ\Theta)

We say f(n) = Θ\Theta(g(n)) iff there exist some constants c1_1 and c2_2, and n0n_0 such that c1_1.g(n) <= f(n) <= c2_2.g(n) for all n >= n0n_0

g(n) will be both the upper and lower bound for f(n), for certain constants c1_1 and c2_2.

Little-o (o)

We say f(n) = o(g(n)) iff f(n) < c.g(n) for any c>0.

f is dominated by g asymptotically.

Little-omega (ω\omega)

We say f(n) = ω\omega(g(n)) iff f(n) > c.g(n) for any c>0.

g is dominated by f asymptotically.

Note the following relation between different n terms:

results matching ""

    No results matching ""