Lecture Notes for Advanced Programming I

26 January 2006 • Programming Economics

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.