Measuring growth

• different functions / implementations run in a different amount of time (in terms of nr. of operations - independent of the computer)

Patterns of growth

• common patterns for how functions grow

• use multiple inputs to identify the overall pattern

Common patterns

• Constant growth - # operations is the same, regardless of the input size, eg. square (X)

• Linear growth - increasing input by 1 adds a constant amount to the number of operations

• Logarithmic growth - # operations grows only when input is multiplied (doubled, tripled, ...)

• Exponential growth - increasing input by 1 doubles (or triples, quadruples) # of operations

Measuring, improving performance

• requires clever thought - often the 1st implementation is not the best

• some tools to improve - ie. memoization

• Measuring:

  • for an iterative program - identify how many times you need to go through the loop before exiting

  • recursive program - env. diagram or call tree