# Asymptotic Analysis

**Bart Massey**

### Performance of Algorithms:

Algorithms run on instances

Performance varies with instance size, "difficulty"

- Key performance measures: time, space (memory/storage)
- "big-O" notation family captures gross change with size

Difficulty of problem is worst-case difficulty of instances

Difficulty of instance is performance of best-possible-performing algorithm

### Big-O

Upper bound on a function

f(n) in O(g(n)) === exists c, n0 . forall n > n0 . 0 <= f(n) <= c * g(n)

Example:

*7*n*in^{2}+n+1*O(n*because when^{2})*n > 10*we find that*7*n*^{2}+n+1 <= 8*n^{2}Note the restrictions, in particular "for sufficiently large n"

Note "in" vs "=". There's a whole thing here.

Common classes:

*O(1), O(lg n), O(n), O(n lg n), O(n*^{2}), O(n^{k}), O(2^{n}), O(n^{n})

### Big-O captures approximate scaling

Assume

*f*in*O(n*and^{2})*f(5) = 37*Then

*f(10) = 37 * 2*?^{2}= 148No! But we can assume that it is a reasonable upper bound

### Big-O and tractability

One of many tables of this kind of thing:

```
n lg n n lg n n^2 n^3 2^n n!
2 1 2 4 8 2 2
4 2 8 16 64 16 24
8 3 24 64 512 256 40,320
16 4 64 256 4096 65536 2.1e13
32 5 160 1024 32768 4.3e9 2.6e35
64 6 184 4096 2.6e5 1.8e19 1.3e89
128 7 896 16384 2.0e6 3.4e38 3.8e215
```

### The Assumptions Of Big-O

The big-O of an algorithm is independent of the machine it is implemented on

The scaling at sizes of interest is the big-O scaling

At least some representative instances scale like big-O

Lower-order factors don't matter

Roughly,

*f(n)*in*O(n*is tractable, others are not^{k})

### big-Ω

Lower bound on a function

*f(n)*in*Ω(g(n)) === exists c, n0 . forall n > n0 . 0 <= g(n) <= c * f(n)*

### big-Θ

Two-sided bound on a function

*f(n) in Θ(g(n)) === f(n) in O(g(n)) and f(n) in Ω(g(n))*

### Asymptotic sums

Sum is maximum:

*f1*in*O(g1)*and*f2*in*O(g2)*=>*f1 + f2*in*O(max(g1, g2))*Also true for Ω, Θ

### What is "n"?

Measure of instance size (info content)

Example: squaring

*O(1)*: "numbers are atomic and CPUs multiply"*O(|n|^2) = O((lg n)*: "numbers are in binary, multiplication uses constant-time additions, grade-school algorithm"^{2})*O(n*|n|) = O(n lg n)*: "numbers are in binary, repeated-addition algorithm"

### Worst case, best case, average case

When analyzing algorithms

Best case is not usually useful

Average case is hard to compute, only useful if know what instances to average over

Worst case is the thing