Algorithm analysis and complexity

What is it?

Formulas

$$T(n) = aT(n/b) + \Theta(n^c) \implies T(n) = \begin{cases}\Theta(n^c) & c > \log_b a\\ \Theta(n^c\log n) & c = \log_b a\\ \Theta(n^{\log_b a}) & c < \log_b a\end{cases}$$

master theorem

Why does it matter?

The mathematics behind it

• Logarithmic functions★★★★★fundamental

  Binary search is $O(\log n)$ and comparison sorting $\Theta(n \log n)$.

• Limits at infinity★★★★★fundamental

  $f = \Theta(g)$ when $f(n)/g(n)$ stays between positive constants as $n \to \infty$.

• Geometric series★★★★★fundamental

  Amortized analysis of dynamic arrays and the master theorem cases are geometric sums.

• Orders of growth★★★★★fundamental

  Choosing between an $O(n^2)$ and an $O(n \log n)$ algorithm is a comparison of orders of growth.

• Asymptotic notation (O, o, Ω, Θ)★★★★★fundamental

  The standard language for running time and memory: $O(n)$, $\Theta(n\log n)$, $\Omega(n)$ lower bounds.

• Inequalities★★★★★frequent

  Upper and lower bounds on running time are proved by chains of inequalities.

• Exponential functions★★★★★frequent

  Brute-force search over $n$ bits takes $2^n$ steps: exponential time is the signature of intractability.

• Limit of a function★★★★★frequent

  Asymptotic comparisons of running times are limits as $n \to \infty$.

• Numerical series★★★★★frequent

  Costs of loops and recursions are sums; harmonic numbers give quicksort's $\Theta(n\log n)$ average.

• Integral test★★★★★frequent

  Turning sums like $\sum_{k\le n} \log k$ into integrals gives $\log n! = n\log n - n + O(\log n)$.

• Polynomial functions★★★★★frequent

  "Polynomial time" $O(n^k)$ is the dividing line between tractable and intractable problems (P).

• Sequences★★★★★frequent

  The running time $T(n)$ is a sequence, often defined by a recurrence such as $T(n) = 2T(n/2) + n$.

• L'Hôpital's rule★★★★★frequent

  Proves the growth hierarchy used to compare algorithms: $\log n = o(n^\varepsilon)$, $n^k = o(2^n)$.

• Power series★★★★★advanced

  Generating functions $\sum a_n x^n$ solve recurrences and count structures in the analysis of algorithms.

• Comparison tests★★★★★frequent

  Bounding a messy cost sum by a simpler one is exactly how asymptotic bounds are proved.

• Bisection method★★★★★indirect

  Same idea as binary search (and git bisect): halving gives $O(\log n)$ steps.