| |
Big-O notation | page 6 of 6 |
Performance of sorting and searching operations with
collections of size n is measured using Big-O notation.
The notation describes the complexity of the algorithm in
relation to the maximum time in which an algorithm operates, for
large values of n. For instance, if you iterate through
an entire collection to find an element, the Big-O notation is
referred to as O(n) , meaning that as n
increases, time to find an element in a collection of size n
increases linearly. This demonstrates that Big-O notation assumes
worst case performance. It is always possible that performance is
quicker. The following table shows the Big-O values for different
operations, with 65,536 as the value for n. In
addition, the operation count shows that if you are going to perform multiple
search operations on a collection, it is faster to do a quick sort on the
collection, prior to searching, versus doing a linear search each time.
(And, one should avoid bubble sorting, unless n is really small!) Description | Big-O | # Operations | Example |
---|
Constant | O(1) | 1 | Hash table lookup (ideal) | Logarithmic | O(log base 2 of n) | 16 | Binary search on sorted collection | Linear | O(n) | 65,536 | Linear search | Linear-logarithmic | O(n x log base 2 of n) | 1,048,576 | Quick sort | Quadratic | O(n x n) | 4,294,967,296 | Bubble sort |
Legend: n = 65536
|