# Note2-AofA: A scientfic Approach

# 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

- 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

Hypothsieze that the cost is ~ $aC_n$ where a is a constant

- 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

- 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:

- Model may not be realistic.
- A challenge in any scientific discipline
- Advantage in CS: we can randomize to make the model apply.

- Math may be too difficult
- A challenge in any scientific (c.f statistical physics)
- A “calculus” for AofA is the motivation for this course!

- 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