The two main things we look at when analyzing algorithms are Time and Space. How much time does the program take to run? How much memory does it use?
We use experimental analysis when we don’t have pseudocode of an algorithm to analyze, we only have results
Experimental analysis is not always accurate
- Different machines can have varying runtimes, so looking at the time it takes to execute on one computer could be different from another
- There can be other processes (noise) interfering with the algorithms runtime
- In general it’s not always going to be precise

Power Law

The Power Law states that $T (n) = a n^{b}$
If we plot n vs T(n) using a log log scale (take the log of both and plot that) and it ends up as a straight line, that means that the power law is at play

Doubling Hypothesis

If the ratio between two consecutive entries in a table of input sizes/runtimes, then its a good hint that there is a polynomial based runtime
Example
We can see that each time the input size is tripled, the runtime is increased by a factor of roughly 9.
A reasonable prediction for an input size of 67500 would be 9 times the previous runtime, $T (67500) \approx 1896.8 * 9 = 17071.2$
If we assume the power law is in effect then we can find the runtime in terms of n
$T (3 n) = 9 T (n)$ - Tripling input size increases runtime by factor of 9
$a (3 n)^{b} = 9 a n^{b}$
$3^{b} n^{b} = 9 n^{b}$
$3^{b} = 9$
$b = 2$