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(n2) – 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(n2) and if it is achieved by 3 nested loops, then the algorithm is said to perform with O(n3) and so on..
O(n3) – Polynomial Time
Examples:
1). Given a expression 23n3 + 12n2 + 9, and n = large numbers, the execution time for n3 increases drastically which takes O(n3) to perform the operation.
O(an) 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(n2) < O(n3) <O(an)
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.