Comparing Time Complexities

Algorithm Best case Worst case Average case
Binary search O( 1 ) O(lg n) O(lg n )
Sequential search O( 1 ) O( n ) O( n )
Finding largest O( n )O( n ) O( n )
Pattern matching O( n ) O( mn ) O( n )
Selection sort O( n2) O( n2) O( n2 )

Typically, we look at the worst case column to compare the efficiency of algorithms.

Binary search is clearly superior to sequential search and sorting seems more expensive that searching or finding maxima.


CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000