C++ Notes: Algorithms: Big-Oh Examples

Here are some big-oh values for typical algorithms.


Here is a table of typical cases.

Type of SearchBig-OhComments
Linear search array/vector O(N)  
Binary search sorted array/vector O(log N) Requires sorted data.
Search balanced treeO(log N)  
Search linked list O(N)  
Search hash table O(1)  

Other Typical Operations

access front O(1) O(1)
access back O(1) O(1)
access middle O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert in middleO(N) O(1)

Sorting arrays/vectors

Some sorting algorithms show variability in their Big-Oh performance. It is therefore interesting to look at their best, worst, and average performance. For this description "average" means uniformly distributed values. The distribution of real values for any given application may be important in selecting a particular algorithm.

Type of SortBestWorstAverageComments
BubbleSort O(N) O(N2)O(N2) Not a good sort, except with ideal data.
Selection sortO(N2)O(N2)O(N2) 
QuickSort O(N log N) O(N2)O(N log N) Good, but it worst case is O(N2)
HeapSort O(N log N) O(N log N) O(N log N) Typically slower than QuickSort, but worst case is much better.

Example. I had to sort a large array of numbers. The values were almost always already in order, and even when they weren't in order there was typically only one number that was out of order. Only rarely were the values completely disorganized. I used a bubble sort because it was O(1) for my "average" data. This was many years ago when CPUs were 1000 times slower. Today I would simply use the library sort for the amount of data I had because a difference in execution time would probably be unnoticed. However, there are always data sets which are so large that a choice of algorithms really matters.

What's missing here


Well, I'll fill things in here as I have time, but don't hold your breath.