tpop(2.5): O-Notation

2.5 O-Notation

2011-03-14 Mon

• We need a way to make such statements more precise, while at the same time abstracting away details like the CPU speed and the quality of the compiler.
• We want to compare running times and space requirements of algorithms independently of programming language, compiler, machine architecture, processor speed, system load, and other complicating factors.

O-notation's basic parameter is n, the size of a problem instance, and the complexity or running time is expressed as a function of n. The ``O'' is for order, as in ``Binary search is O(log n); it takes on the order of logn steps to search an array of n items.''

The notation O(f(n)) means that, once n gets large, the running time is proportional to at most f(n), for example, O(n²) or O(nlog n).

Asymptotic estimates like this are valuable for theoretical analyses and very helpful for gross comparisons of algorithms, but details may make a difference in practice.

We must also distinguish between worst-case and expected behavior. It's hard to define ``expected,'' since it depends on assumptions about what kinds of inputs will be given.

Quicksort's worst-case run-time is O(n²) but the expected time is O(n log n). By choosing the pivot element carefully each time, we can reduce the probability of quadratic or O(n²) behavior to essentially zero; in practice, a well-implemented quicksort usually runs in O(n log n) time.

O-Notation

Notation	Name	Example
O(1)	constant	array index
O(log n)	logarithmic	binary search
O(n)	linear	string comparison
O(nlog n)	nlogn	quicksort
O(n2)	quadratic	simple sorting methods
O(n3)	cubic	matrix multiplication
O(2n)	exponential	set partitioning

• Accessing an item in an array is a constant-time or O(1) operations.
• An algorithm that eliminates half the input at each stage, like binary search, will generally take O(long n).
• Comparing two n-character strings with strcmp is O(n).
• The traditional matrix multiplication algorithm takes O(n³), since each element of the output is the result of multiplying n pairs and adding them up, and there are n² elements in each matrix.
• Exponential-time algorithms are often the result of evaluating all possibilities: there are 2ⁿ subsets of a set of n items, so an algorithm that requires looking at all subsets will be exponential or O(2ⁿ).