Algorithmic analysis: express the "cost" of a program (time, space, etc.) as a function of the inputs.
We can use asymptotics to compare these cost functions to each other.
Empirical analysis: use a clock (or a relevant tool) to measure the cost on different inputs.
Depending on how the program is run (computer power, other programs, etc.), can vary!
Program to time sorting code: timer.SortTiming
Sometimes, we measure costs of a single call to a function. Other times, we're concerned with the average runtime, because the worst-case doesn't occur often. (Lecture 17)
Example: dynamic resizing arrays
Program to time amortization: timer.AmoritzationTiming
Whiteboard BST review during lab
class A implements Comparable<A> {
@Override
public int compareTo(A other) { ... }
}
A a1 = new A();
A a2 = new A();
if (a1.compareTo(a2) < 0) {
// a1 < a2
} else if (a1.compareTo(a2) > 0) {
// a1 > a2
} else if (a1.compareTo(a2) == 0) {
// a1 == a2
}