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.

[Prev][TOC][Next]

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