Computer Algorithms II Lecture Notes

2 October 2007 • Performance Estimation

Actually, a partial hierarchy of function behavior. This

• Constant - bigoh(1), array indexing

• Log - O(log n), binary search

• Linear - bigoh(n), linear search

• Log-linear - O(n log n), heapsort

• Quadratic, square - O(n²), bubble sort

• Cubic - O(n³), matrix multiplication

• Exponential - O(2ⁿ), optimal route finding

is a more complete hierarchy of common asymptotic behaviors for functions. No hierarchy of asymptotic behaviors can ever be complete because each algorithm has a distinct asymptotic characterization, particularly as the analysis gets more detailed. However, every asymptotic characterization can be slotted, with more or less accuracy, in the hierarchy given above.

This page last modified on 24 January 2006.