Algorithmic Growth

Order of Growth

Algorithmic efficiency is a function of time and required memory. All too often brute force approaches are used because it is relatively easy to construct and one that actually can provide proof of correctness. However, more clever polynomial time bounded approaches would provide a more efficient solution. The order of growth or rate of growth for an algorithm considers its running time. Only the leading term of a polynomial is required and constants and constant coefficients are insignificant. So a time of xn² + yn + c yields a rate of growth of θ(n²). An algorithm would be more efficient than another one if its worst-case time has a lower order of growth. Keep in mind that this is for large inputs.

Asymptotic Efficiency

Various measures such as worst-case, average-case and best-case asymptotic complexity are used to indicate algorithmic efficiency. Asymptotic complexity itself refers to the function of computational time growth in a problem size as its size approaches infinity. Asymptotic efficiency deals with the increasing running time of an algorithm with respect to increases in the size of its input. Asymptotic running time notation is defined by functions having a domain of the natural numbers.

θ notation

k₂g(n)

θ notation represents an upper and lower asymptotic "tight" bound for a given function f(n). So given a function g(n), θ(g(n)) = {f(n) | $ constants k₁, k₂ and n₀ > 0 where 0 ≤ k₁g(n) ≤ f(n) ≤ k₂g(n) for every n ≥ n₀}. So the running time in θ notation can be anywhere from its lower bound to its upper bound.

f(n) = θ(g(n)) The notation is actually f(n) Î θ(g(n)).

O notation

O notation represents an upper asymptotic bound only. So given a function g(n), O(g(n)) = {f(n) | $ constants k and n₀ > 0 where 0 ≤ f(n) ≤ kg(n) for every n ≥ n₀}. In other words, f(n) has an upper bound of some constant k multiple of g(n). So the running time in terms of O notation is always going to be the upper bound. In other words, we always know that the running time is going to be at the most the upper bound. As an example, O(n²) implies that if a computation of size n takes t units of time then a computation size of 2 * n would take 4 * t units of time. For a computation problem of O(n³), if the problem size doubled then the computation time would increase by a factor of 8.

f(n) = O(g(n)) The notation is actually f(n) Î O(g(n)).

Ω notation

Ω notation represents a lower asymptotic bound only. So given a function g(n), Ω(g(n)) = {f(n) | $ constants k and n₀ > 0 and 0 ≤ kg(n) ≤ f(n) for every n ≥ n₀}. So the running time in terms of Ω notation is always going to be the lower bound. In other words, we always know that the running time is as at least the lower bound.

f(n) = Ω(g(n)) The notation is actually f(n) Î Ω(g(n)).

Links

http://www.nist.gov/dads/HTML/bigOnotation.html
http://www.me.berkeley.edu/~e77/lecnotes/ch20/ch20.htm
http://www.cs.wisc.edu/~hasti/cs367-common/notes/COMPLEXITY.html