Asymptotic Analysis

how does the running time scale with the size of the input notation:

$$n$$: size of input, $$T(n)$$: running time of algorithm on input of size $$n$$

Definitions

T(n) ∈ O(f(n)) if there exist constants $$c,n0 > 0$$ such that $$T(n) ≤ cf(n)$$ for all $$n > n0$$.

• $$T(n)$$ is upper bounded by (one of) $$O(f(n))$$'

T(n) ∈ Ω(f(n)) if there exist constants $$c,n0 > 0$$ such that $$T(n) ≥ cf(n)$$ for all $$n > n0$$.

• $$T(n)$$ is lower bounded by (one of) $$Ω(f(n))$$'

T(n) ∈ Θ(f(n)) if $$T(n) ∈ O(f(n))$$ and $$T(n) ∈ Ω(f(n))$$.

T(n) ∈ o(f(n)) if for all constants $$c > 0$$, there exists $$n0 > 0$$ such that $$T(n) < cf(n)$$ for all $$n > n0$$.

Intuitions

• O is like ≤, Ω is like ≥, Θ is like =, and o is like <. There is also a similar notation ω that corresponds to >.
• $$n > n0$$ should be interpreted as $$n$$ sufficiently larger, understood as $$n$$ is equal to some extremely small number $$\epsilon$$

Computation

$$lim_{n\to\infty}\frac{T(n)}{f(n)}$$

• limit = 0, then T(n) = o(f(n)) and T(n) = O(f(n)).
• limit > 0, then T(n) = Θ(f(n)) (and T(n) = O(f(n)) and T(n) = Ω(f (n)))
• limit $$\to\infty$$, then T(n) = ω(f(n)) and T(n) = Ω(f(n))
• limit doesn't exist? Check definitions then decide!

Note

• Any exponential dominates any polynomial: $$3^n$$ dominates $$n^5$$ (it even dominates $$2^n$$).

• Any polynomial dominates any logarithm: $$n$$ dominates $$\log^3{n}$$ or $$n^2$$ dominates $$n\log{n}$$, or $$lim_{n\to\infty}\frac{\log(n)^k}{n} = 0$$ for any constant $$k$$

Stirling’s approximation: (p.58 of introduction to algorithm)

$$n! \geq (\frac{n}{e})^n \ n! = o(n^n) \ n! = w(2^n) \ lg(n!) = \Theta(n\lg{n})$$