Basic observational models for algorithms

0-doubling-hypothesis.md

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).

##Doubling Hypothesis This is used to determine the variables of a power law quickly:

T = a*N^b

Methodology

1. Run algorithm many times, doubling inputs with each run.

2. Note the run time for each.

3. Take the ratios between consecutive runtime.

4. If the ratios converge to a value, take the log of that value.

   b = log

   (ratio) if the values to do not converge, the relationship is not a power-law relationship

5. Run the algorithm many times with different values of N to get values of T.

6. Solve for a for each of these. Possibly take an average.

   • b is known, we have values of N and T

line-fitting.md

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).

##Predictions Based on line-fitting

Methodology

1. Run algorithm with different sized inputs.
2. Note the run time for each.
3. Plot a time-input graph and fit a line to the points.
   • The relation is often logarithmic, so try fit a line on log-log plot also
4. Solve the line of best fit to get time in terms of input.