# A scientfic Approach

The scientfic method: O-notation, not at all useful for predicting performance

Scientific method calls for tilde-notion. Running time is ~aN^c, an effective path to predicting performance

Common error: Thinking that O-notaion is useful for predicting performance

## Galactic algorithms:

R.J.Lipton: A galactic is one that will never be used. An effect would never be noticed in this galaxy. 75% SODA,95% STOC/FOCS are galctic

## Steps

1. Analyze the algorithm by
• idenfiying anabstractr operation in the inner loop
• Develop a realistic model for input to the program.
• Analyze the frequeny of execution $C_n$ of op for input size N
2. Hypothsieze that the cost is ~ $aC_n$ where a is a constant

3. Validate the hypothesis by
• Developing generator for input according to model.
• Calculate a by running the program for large input.
• Run the program for larger input check the analysis
4. Validate the model by testing in application contexts.

Refine and repeat as necessary.

Tilde Notation.

### Empirical:

* Run algorithm to solve real algorithm
* Measure running time and/or count operations Challenge: need good implementation


### Mathematical:

* Develop mathematical model.
* Analyze algorithm within model Challenge: need good model. need to the math


### Scientific:

* Run algorithm to solve real problem
* Check for agreement with model. Challenge: need all of the above.


## Drawbacks:

1. Model may not be realistic.
• A challenge in any scientific discipline
• Advantage in CS: we can randomize to make the model apply.
2. Math may be too difficult
• A challenge in any scientific (c.f statistical physics)
• A “calculus” for AofA is the motivation for this course!
3. Experiments may be too difficult.
• Not compared to other scientific disciplines.
• Can’t implement? Why analyze?

symmetry:

$\sum_{1 \leq k\leq N} {C_{k-1}+C_{N-k}}$

both sums are $\sum_{1 \leq k \leq 2} C_{k-1}$

Quicksort compares: limiting distribution is not “normal” “Approximating the Limiting Quicksort Distributution”

Easy Method to Predict Hypothesis: Running time of Quicksort is ~aN in N.

Experiment.

* Run for input size N. Observe running time.
* Could solve for a.
* Predict time for 10N to increase by a factor ..


Validate-refine-analyze cycle

ALGO