Order-of-magnitude time efficiency summary

1

1

best case for sequential search

n

worst case for sequential search

n

average case for sequential search

1

best case for binary search

lg n

worst case for binary search

lg n

average case for binary search

n²

best case for selection sort

n²

worst selection sort

n²

average selection sort

n

best shuffle left

n²

worst shuffle left

n²

average shuffle left

n

best copy over

n

worst copy over

n

average copy over

n

best converging pointers

n

worst converging pointers

n

average converging pointers

n

best pattern matching

m x n

worst pattern matching