Thursday, December 23, 2010

Visualizing Big-O complexity functions

I quickly threw this little Silverlight application together to help visualize some of the common Big-O complexity functions often quoted in any discusion on Data Structures and Algorithms.

This works on Linux Firefox with Moonlight 3 Preview Release it is a little slow but it works.

The following is a brief summary of the functions demonstrated in the application. You can get more detail here.
FunctionDescriptionExample
O(1) Constant complexity regardless of the domain size. Array direct indexing, Hash table
O(n) Linear complexity. As the domain size increases, the time/complexity increases linearly. If you double the items the complexity will double. Sequential search
O(log n) Logarithmic complexity. As the domain size increases, the time/complexity increases logorithmically Binary Search on sorted data, Lookup in balanced binary tree
O(n log n) Log Linear complexity. As the domain size increases, the time/complexity increases at a log linear or geometric rate. Heap Sort, Merge Sort, Quick Sort1
O(n²) Quadratic complexity. As the domain size increases, the time/complexity increases quadratically. Bubble Sort, Insertion sort
O(n³) Cubic complexity. As the domain size increases, the time/complexity increases at a cubic rate. Naive multiplication of two nxn matrices.
O(2ⁿ) Exponential complexity. As the domain size increases, the time/complexity increases exponentialy. Some graph algoritms like finding the exact solution to the traveling salesman problem.
1Quick sort has best and average case of O(n log n) but worst case of O(n²)