Analysis of Performance (Time)
Considerations
- Size of problem (specified as input)
- Software environment
- Computer
Principles
- Performance isn't critical for small problems
- Growth as a function of input size is most critical
- Second-order terms can (usually) be ignored
Capturing growth
All are a function of input size
- Exact expression of frequency of most repeated instruction
- Expression so that when divided by actual performance the ratio approaches 1 for increasingly larger input sizes (tilde approximation, see p. 179)
- Expression provides an upper bound on performance, using a constant multiplier, for large enough input size (asymptotic performance, aka big-O notation, see p. 207)
Example: Sequential search
for (int i = 0; i < dictionary.length; i++) {
if (str.equals(dictionary[i])) {
return true;
}
}
return false;
Analysis
- Input size: size of the array being search (dictionary.length)
- Best case: one comparison (constant time)
- Worst case: N comparisons (linear time)
- Average time?
For worst case, tilde approximation and asymptotic notation are the same: f(N) = N