Order of an algorithm

Objectives

  • Discuss algorithm complexity
  • Explain what the "order of an algorithm" means
  • Comapre and contrast different orders

Algorithm efficiency (Order)

  • See Gerald W. Kruse's course notes on algorithm efficiency
  • See the Cprogramming.com article on the order of algorithms
  • Big O notation: a measure of algorithm efficiency which describes relatively how much time will be taken to complete the algorithm related to the size of the data set
  • If the order of algorithm A is n2 and the order of algorithm B is n log n, there are implications:
    • Log n in computer caculations is usually base 2 log, but that detail doesn't matter for ordinary comparisons of algorithm complexity
    • When the number of data items (n) is small, the difference in the order of the algorithms probably won't matter much since other efficiencies and overhead will probably have an even greater effect than the order
    • For large data sets (large n), algorithm B has a distinct advantage
    • Estimated relative runtimes:
      nAlg A runtimeAlg B runtime
      1010033
      10010,000664
      1,0001,000,0009,966
      10,000100,000,000132,877
      100,00010,000,000,0001,660,964
      1,000,0001,000,000,000,00019,931,569
    • For small data sets, the increase in algorithm complexity which is often needed to achieve a better algorithm order may not be worth the effort - it may depend on how often the containing application is run
  • If you find some algorithms with their order specified, here is a list of common orders from best to worst
    • 1
    • log n
    • n
    • n log n
    • nc (where n2 beats n3 beats n4, etc.)
    • an (where 2n beats 3n beats 4n, etc.)
    • N! (factorial)
    • Nn

Graphic example of order growth

chart showing growth for various orders of complexity
Chart showing growth for various orders of complexity