Big O, Omega and Theta Notations are used to describe not only the way an algorithm performs but the way an algorithm scales to produce a output. It measures the efficiency of an algorithm with respect to time it takes for an algorithm to run as a function of a given input. They are used to determine the Worst case complexity, Best case complexity and the Average case complexity.

Big Omega notation describes the **best** case of a running algorithm. In contrast, Big O notation describes the **worst **case of a running algorithm.

**Big O Notation** is denoted as O(n) also termed as Order of n, or also termed as O of n.

**Big Omega Notation** is denoted as Ω(n) also termed as Omega of n.

Apart from Big O (O) and Big Omega (Ω), there are Big Theta (Θ), Small O (*o*) and Small Omega (ω) notations that are used in computer science programming. You can get more information from http://en.wikipedia.org/wiki/Big_O_notation#Big_Omega_notation.

**O(1) – Constant Time**

This means that the algorithm requires the same fixed number of steps regardless of the size of the task.

Examples:

1). Finding an element in a HashMap is usually a constant time, which is O(1). This is a constant time because, a hashing function is used to find an element, and computing a hash value does not depend on the number of elements in the HashMap.

2). Push and Pop operations for a stack containing n elements.

3). Insert and Remove the operations of a queue.

**O(log n) – Logarithmic Time**

This means that the algorithm requires the Logarithmic amount of time to perform the task.

Examples:

1). Binary search in a sorted list or Array list of n elements.

2). Insert and Find operations for a binary search tree with n nodes.

3). Insert and Remove operations for a heap with n nodes.

4). Fast insertion, removal and lookup time of a TreeMap (a.k.a balanced tree because a TreeMap maintains key/value objects in a sorted order by using a red black tree) is O(log n)

**O(n) – Linear Time**

This means that the algorithm requires a number of steps directly proportional to the size of the task.

Examples:

1). Traversal or searching of a list(a linked list or a array) with n elements. This is linear because you will have to search the entire list. This means that if a list is twice as big, searching will take twice as long.

2). Finding the maximum or minimum element in a list, or sequential search in an unsorted list of n elements.

3). Traversal of a tree with n nodes.

4). Calculating iteratively n-factorial, for example finding iteratively the nth Fibonacci number.

**O(n log n) – N times Logarithmic time**

This means that the algorithm requires N times the Logarithmic time of solving a algorithm.

Examples:

1). Advanced Sorting Algorithms like quick sort and merge sort.

**O(n ^{2}) – Quadratic Time**

Examples:

1). Simple sorting algorithms, for example a selection sort of n elements.

2). Comparing 2 two dimensional arrays of size n by n.

3). Finding duplicates in an unsorted list of n elements.

**Note: If a solution to a problem has one single iteration, in other words, if the solution is achieved by either only one for loop or one while loop or one do-while loop or a single recursive function, then that algorithm is said to perform with O(n) else if the solution is achieved by 2 nested loops, then the algorithm is said to perform with O(n ^{2}) and if it is achieved by 3 nested loops, then the algorithm is said to perform with O(n^{3}) and so on..**

**O(n ^{3}) – Polynomial Time**

Examples:

1). Given a expression 23n^{3} + 12n^{2} + 9, and n = large numbers, the execution time for n^{3} increases drastically which takes O(n^{3}) to perform the operation.

**O(a ^{n}) for a > 1 – Exponential Time**

Examples:

1). Recursive Fibonacci implementation

2). Problem to solve Towers of Hanoi

3). Generating all permutations of n symbols.

Here is the order of execution time, in which the way Big O notations worst case behavior is determined.

**O(1) < O(log n) < O(n) < O(n log n) < O(n ^{2}) < O(n^{3}) <O(a^{n})**

**Constant Time < Logarithmic Time < Linear Time < N times of Logarithmic Time < Quadratic Time < Polynomial Time < Exponential Time.**

If algorithm is __ then its performance is __

algorithm | performance |
---|---|

o(n) | < n |

O(n) | ≤ n |

Θ(n) | = n |

Ω(n) | ≥ n |

ω(n) | > n |

##### 4 important Big O rules:

1). If you have 2 different steps in your algorithm, add up those steps

Example:

function something() { doStep1(); // O(a) doStep2(); // O(b) }

Overall runtime: O(a+b)

2). Drop Constants

function minMax1(array) { min, max = null for each e in array min = MIN(e, min) //O(n) for each e in array max = MAX(e, max) //O(n) }

Another example:

function minMax2(array){ min, max = null for each e in array min = MIN(e, min) max = MAX(e, max) }

Overall runtime: O(2n)

So dropping the constants overall runtime equals to O(n)

3). Different Arrays is equivalent to (=>) Different Variables.

function getSize(arrayA, arrayB){ int count = 0; for a in arrayA{ for b in arrayB{ if(a == b){ count = count++; } } } return count; }

Overall runtime is NOT O(n^2), but instead it is O(a * b)

Note that, the loops are emulated on 2 different array’s.

4). Drop non dominant terms.

function printSize(array){ max = null; // runtime for the below loop is O(n) for each a in array{ max = MAX(a, max); } //runtime for the below nested loop is O(n^2) for a in array{ for b in array{ print a, b; } } }

Overall runtime: O(n + n^2)

However, since O(n) is too small and can be neglected.

In other words,

O(n^2) <= O(n + n^2) <= O(n^2 + n^2)

O(n^2) <= O(n + n^2) <= O(2 * n^2)

Now, dropping the constants based on Rule 2,

O(n^2) <= O(n + n^2) <= O(n^2)

if left and right are equivalent, then center is too..

i.e O(n + n^2) is equivalent to O(n^2)

Hence, overall runtime is O(n^2)

Sources:

This post was more or less taken from the afore mentioned sites, with little or more changes based on my knowledge and observation. I will be adding more examples to one or more above mentioned time analysis Big O notations as and when I come across in the near future of programming career.