Computational Tractability

Brute Force

Brute Force: for many nontrivial probelms, there is a natural brute-force search algorithm that checks every possible solution.

• Typically takes $2^n$ steps (or worse) for inputs of size $n$.
• Unacceptable in practice.

For the stable matching problem: test all $n!$ perfect matchings for stability.

Polynomial Running Time

Desirable scaling property: when the input size doubles, the algoirhtm should slow down by at most some multiplicative constant factor $C$.

An algorithm is poly-time if the above scaling property holds:

• There exists constants $a > 0$ and $b >0$ such that, for every input of size $n$, the algorithm performs $\leq a$ $n^b$ primitive computational steps (corresponds to $C=2^b$).

This doesn't have the desireable scaling property: $f(n) = n!$ $f(2n) = (2n)! = C \times n!$

These have the desireable scaling property: $f(n) = a n^b$ $f(2n) = a(2n)^b = 2^b \times f(n)$ For example, $f(n) = 10 n^3$ $f(2n) = 80n^3 = 8 \times f(n)$ And, $f(n)=3n^2 + 10n + 7$ $f(2n) = 12n^2 + 20n + 7 \leq 4 \times f(n) = 12n^2 + 40n + 28$

We say that an algorithm is efficient if it has a polynomial running time. Theory: Definition is (relatively) insensitive to model of computation In practice, it really works because

• the poly-time algorithms that people develop have both small constants and small exponents.
• breaking through the exponential barrier of brute force typically exposes some crucial structure of the problem.

The exception is that some poly-time algorithms in the wild have galactic constants and/or huge exponents.

Worst-case Analysis

Worst case: the running time guarantee for any input of size $n$.

• This generally represents efficiency in practice
• Draconian (excessively harsh) view, but hard to find effecive alternative

Exceptions: some exponential-time algorithms are used widely in practice because the worst-case instsances don't arise

Other types of analyses

Probabilistic: expected running time of a randomized algorithm.

• Ex: the expected number of compares to quicksort $n$ elements is ~$2n \ln n$

Amortized: worst-case running time for any sequence of $n$ operations

• Ex: starting from an empty stack, any sequence of $n$ push and pop operations takes $O(n)$ primitive computational steps using a resizing array.

There is also: average-case analysis, smoothed analysis, competitive anlysis

Asymptotic Order of Growth

Big O Notation

Represents the upper bounds. $f(n)$ is $O(g(n))$ if there exist constants $c > 0$ and $n_0 \geq 0$ such that $0 \leq f(n) \leq c \cdot g(n)$ for all $n \geq n_0$.

Ex: $f(n) = 32n^2 + 17n + 1$

• $f(n)$ is $O(n^2)$
• $f(n)$ is neither $O(n)$ nor $O(n \log n)$ because there does not exist constants $C$, $n_0$ such that $32n^2 + 17n + 1 \leq C \cdot n$, $\forall n \geq n_0$

Typical usage: insertion sort makes $O(n^2)$ compares to sort $n$ elements.

One-way "equality" $O(g(n))$ is a set of functions, but computer scientists often write $f(n)=O(g(n))$ instead of $f(n) \in O(g(n))$.

• Ex: consider $g_1(n)=5n^3$ and $g_2(n) = 3n^2$
  • we have $g_1(n)=O(n^3)$ and $g_2(n)=O(n^3)$, but we cannot conclude that $g_1(n)=g_2(n)$

Domain and codomain: $f$ and $g$ are real-valued functions.

• The domain is typically the natural numbers $\mathbb{N} \to \mathbb{R}$ where $\mathbb{N}$ represent the input size, recurrence relations.
• Sometimes we extend to the reals: $\mathbb{R}_{\geq 0} \to \mathbb{R}$ where $\mathbb{R}_{\geq 0}$ represent plotting, limits, calculus
• Or restrict to a subset.

The bottom line is that it is okay to abuse notation in this way, but it is not okay to misuse it.

Properties

Reflexivity: $f$ is $O(f)$ Constants: If $f$ is $O(g)$ and $c<0$ then $cf$ is $O(g)$. Products: If $f_1$ is $O(g_1)$ and $f_2$ is $O(g_2)$, then $f_1 f_2$ is $O(g_1g_2)$. The proof is as follows: - $\exists c_1 > 0$ and $n_1 \geq 0$ such that $0 \leq f_1(n) \leq c_1 \cdot g_1(n)$ for all $n \geq n_1$. - $\exists c_2 > 0$ and $n_2 \geq 0$ such that $0 \leq f_2(n) \leq c_2 \cdot g_2(n)$ for all $n \geq n_2$. - Then, $0 \leq f_1(n) \cdot f_2 (n) \leq c_1 \cdot c_2 \cdot g_1(n) \cdot g_2(n)$ for all $n \geq max \{ n_1, n_2\}$. $\blacksquare$

Sums: If $f_1$ is $O(g_1)$ and $f_2$ is $O(g_2)$, then $f_1 = f_2$ is $O(max \{g_1, g_2\})$ (the max will ignore lower-order terms).

• Ex: $f_1 = 100n^{10} = O(n^{10})$ and $f_2 = 51n^5 = O(n^5)$, so $f_1 + f_2 = O(n^{10})$.

Transitivity: if $f$ is $O(g)$ and $g$ is $O(h)$, then $f$ is $O(h)$.

Big Omega Notation

Represents the lower bounds. $f(n)$ is $\Omega (g(n))$ if there exists constants $c >0$ and $n_0 \geq 0$ such that $f(n) \geq c \cdot g(n) \geq 0$ for all $n \geq n_0$.

Ex: $f(n) = 32 n^2 + 17n + 1$.

• $f(n)$ is both $\Omega(n^2)$ and $\Omega(n)$, but is not $\Omega(n^3)$.
• $32m^2 + 17m + 1 \geq 1 \cdot n$, $\forall n \geq 1$ when $c = 1, n_0 = 1$.

Typically used for any compare-based sorting algorithm that requires $\Omega(n \log n)$ compares in the worst case.

Bit Theta Notation

Represents the tight bounds. $f(n)$ is $\Theta(g(n))$ if there exists constants $c_1 > 0$, $c_2 >0$ and $n_0 \geq 0$ such that $0 \leq c_1 \cdot g(n0) \leq f(n) \leq c_2 \cdot g(n)$ for all $n\geq n_0$.

Example: $f(n) = 32n^2+17n+1$.

• $f(n) = \Theta(n^2)$ (choose $c_1 = 32, c_2 =50, n_0=1)$
• $f(n)$ is neither $\Theta(n)$ nor $\Theta (n^3)$

Typical usage: merge sort makes $\Theta(n\log n)$ compares to sort $n$ elements.

Asymptotic Bounds

Proposition: If $lim_{n \to \infty} \frac{f(n)}{g(n)} = c$ for some constant $0<c<\infty$ then $f(n)$ is $\Theta(g(n))$. Proof:

• By definition of the limit, for any $\varepsilon > 0$, there exists $n_0$ such that $c - \epsilon \leq \frac{f(n)}{g(n)} \leq c + \epsilon$ for all $n \geq n_0$.
• Choose $\varepsilon = \frac{1}{2}c > 0$.
• Multiplying by $g(n)$ yields $\frac{1}{2} c \cdot g(n) \leq f(n) \leq \frac{3}{2} c \cdot g(n)$ for all $n\geq n_0$,
• Thus, $f(n)$ is $\Theta(g(n))$ by definition, with $c_1 = \frac{1}{2}c$ and $c_2=\frac{3}{2}c$

Proposition: If $lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$, then $f(n)$ is $O(g(n))$ but not $\Omega(g(n))$. Proposition: If $lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$ , then $f(n)$ is $\Omega(g(n))$ but not $O(g(n))$.

The asymtomatic bounds for some common functions:

Polynomials: Let $f(n) = a_0 + a_1n + \dots + a_dn^d$ with $a_d > 0$. Then, $f(n)$ is $\Theta(n^d)$. Proof:

• $lim_{n\to\infty}\frac{a_0+a_1n+\dots+a_dn^d}{n^d} = a_d > 0$

Logarithms: $\log_a n$ is $\Theta(log_b n)$ (log base does not need to be specified if it is a constant) for every $a > 1$ and every $b > 1$. Proof:

• $\frac{\log_a n}{\log_b n} = \frac{1}{log_b a}$

Logarithms and polynomials: $\log_a n$ is $O(n^d)$ for every $a > 1$ and every $d>0$ Proof:

• $lim_{n \to \infty} \frac{\log_a n}{n^d} = 0$

Exponentials and polynomials: $n^d$ is $O(r^n)$ for every $r > 1$ and every $d>0$ Proof:

• $lim_{n \to \infty} \frac{n^d}{r^n} = 0$

Factorials: $n!$ is $2^{\Theta (n \log n)}$. Proof:

• Stirling's formula says $n! \sim \sqrt{2\pi n})(\frac{n}{e})^n$

Algorithm Analysis

We want to implement the gale-shapley to run in $O(n^2)$ time.

• To represent hospitals and students we index them $1, \dots, n$.
• To represent a matching, we maintain two arrays $student[h]$ and $hospital[s]$. When $h$ is matched with $s$, then $student[h] = s$ and $hospital[s]=h$. Use the value $0$ to designate that hospital or student is unmatched.
  • Can add/remove a pair from matching in $O(1)$ time.
  • Maintain a set of unmatched hospitals in a queue (or stack)
  • Can find an unmatched hospital in $O(1)$ time.

Hospital makes a proposal data representation

• key operaion: find hospital's next favorite student
• for each hospital: maintain a list of students, ordered by preference
• for each hospital: maintain a pointer to student for next proposal.
• making a proposal takes O(1) time.

Student accepts/rejects a proposal data representation

• does student $s$ perfer hosiptal $h$ to hospital $h'$?
• for each studnet, create inverse of preference list of hospitals. (a ranking list).
• after $\Theta(n^2)$ preprocessing time (to create the $n$ ranking arrays), it takes $O(1)$ time to accept/reject a proposal.

Theorem: we can implement Gale-Shapley to run in $O(n^2)$ time. Proof:

• $\Theta(n^2)$ preprocessing time to create $n$ ranking arrays.
• There are $O(n^2)$ proposals; processing each proprosla takes $O(1)$ time.

Common Running Times

Constant time has running time of $O(1)$.

• this means that the runtime does not depend on the input size $n$.
• e.g., conditional branch, arithmetic/logic operation, declare/initialize variable

Linear time has running time of $O(n)$.

• e.g., merge two sorted list.

Logarithmic time has running time of $O(\log n)$.

• e.g., search in a sorted array, binary search

Linearithmic time has running time of $O(n \log n)$.

• e.g., given an array of $n$ elements, rearrange them in ascending order, mergesort

Quadratic time has running time of $O(n^2)$.

• e.g.,: closest pair of points. Given a list of $n$ points in a plane $(x_1, x_2), \dots, (x_n,y_n)$, find the pair of points that is closest to each other; enumerate all pairs of points.

Cubic time: running time is $O(n^3)$.

• e.g., 3 sym, enumerate all triples

Polynomial time: running tim eis $O(n^k)$ for some constant $k >0$.

• E.g., Independent set of size $k$ (a constant). Given a graph, find $k$ nodes such that no two are joined by an edge; enuermate all subsets of $k$ nodes, the number k-elemet subsets is n-choose-k.

Exponential time: running time is $O(2^{n^k})$ for some constant $k>0$.

• e.g., euclidean TSP (given $n$ points in th eplane, find a tour of minimum length); $O(n \times n!)$ algorithm. Enumerate all permutations of length n.