Experimentally determine the runtime of algorithms. All data shown in generated using javascript as you watch. Feel free to add a new sorting function yourself!

Experimental Algorithmics is a field that tries to experimentally measure the running time of various algorithms. While best-fit methods can of course be used, here is a simple starting rule of thumb. Start with an input size that takes at least 1 second to process. Double the input size.

  1. If the run time increases by 1x (doesn't change), your algorithm may be constant time.
  2. If the run time increases by 2X, your algorithm is linear-time.
  3. If the run time increases by 4X, your algorithm is quadratic.
  4. If the run time increases by 8X, your algorithm is cubic.
  5. If the run time increases by <2X, your algorithm is sub-linear (for example, logarithmic).
  6. If the run time increases by a little more than 2X, your algorithm may have a runtime like O(n log n)
Verify with a few more tests. If you don't get consistent results, there may be a random element, or you may be crossing some important threshold (for example, running out of RAM and starting to use swap memory).

For the examples shown here, I picked sorting because it is a well-studied problem most programmers are taught in school.