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”