See also: Algorithm | Data structure | Programming
Wikipedia: Big O Notation
Pronounced: “Big Oh”
A notation for measuring efficiency of some operation, especially in algorithm analysis and data structures.
A Big O statement will denote rate of growth of the operation, which essentially indicates that operation’s behavior in the worst case (say, a failed search of a binary tree). The N in a Big-O function indicates the N number of items in a structure; thus the time taken to do an operation is often proportional to the size of the input.
Computer Scientists seek to design O(1) algorithms; that is, constant time algorithms, since these algorithms are more efficent (in fact, the most efficient) in relation to the size of input.
Typical Growth Rates
- function
- name
- c
- constant
- log N
- logarithmic
- log^2 N
- log-squared
- N
- linear
- N log N
- N^2
- quadratic
- N^3
- cubic
- 2^N
- exponential
Example Rates
- Binary Tree search is logarithmic (O = log N)
- Linked List search is linear (O = N)
- Skip List search is logarithmic (O = log N)
TakeDown.NET -> “Big-O”