CIS 250 - Order of an algorithm

Objectives

• discuss algorithm complexity

Algorithm efficiency (Order)

• see Gerald W. Kruse course notes on algorithm efficiency
• 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 n² 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:

    n	Alg A runtime	Alg B runtime
    10	100	33
    100	10,000	664
    1,000	1,000,000	9,966
    10,000	100,000,000	132,877
    100,000	10,000,000,000	1,660,964
    1,000,000	1,000,000,000,000	19,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
  • n^c (where n² beats n³ beats n⁴, etc.)
  • aⁿ (where 2ⁿ beats 3ⁿ beats 4ⁿ, etc.)
  • N! (factorial)
  • Nⁿ

Graphic example of order growth