0. Asymptotic Notation

Since different computers do operations differently fast, we are interested in how the runtime scales with increasing inputs (how it behaves asymptotically).

Asymptotic Classes

Let $c,c_1,c_2>0$ be some constant and $n\ge 0$ arbitrary.

• $T$ grows at most as fast as $f(n)$: $T(n)\le \mathcal{O}(f(n))⟺T(n)\le c\cdot f(n)$
• $T$ grows at least as fast as $f(n)$: $T(n)\ge \Omega (f(n))⟺T(n)\ge c\cdot f(n)$
• $T$ grows as fast as $f(n)$: $T(n)=\Theta (f(n))⟺c_{1}f(n)\le T(n)\le c_{2}f(n)$

We abuse notation and denote membership in a set by $=,\le ,\ge$.

For proving theta: $T(n)\ge \Omega (f(n))$ and $T(n)\le \mathcal{O}(f(n))⟺T(n)=\Theta (f(n))$

L’Hôpital’s rule

Problem: $\underset{x\to a}{\lim }\frac{f(x)}{g(x)}=\frac{0}{0}$ or $=\frac{\infty }{\infty }$

Solution: $\underset{x\to a}{\lim }\frac{f(x)}{g(x)}=\underset{x\to a}{\lim }\frac{f^{\prime }(x)}{g^{\prime }(x)}$ - Take the derivate of both sides

Pitfalls:

• $f,g$ must be differentiable near the point of interest, except possibly at the point itself.
• Using it even when not getting $0/0$ or $\infty /\infty$

Master Theorem

$a,b,C>0$ and $T:\mathbb{N}\to {\mathbb{R}}^{+}$ a function such that for all even $n\in \mathbb{N}$,

$$T(n)\le aT\left(\frac{n}{2}\right)+C{n}^b$$

Then for all $n=2^k$, $k\in \mathbb{N}$:

1. If $b>{\log }_{2}a$, $T(n)\le O(n^b)$.
2. If $b={\log }_{2}a$, $T(n)\le O(n^{{\log }_{2}a}\cdot \log n)$.
3. If $b<{\log }_{2}a$, $T(n)\le O(n^{{\log }_{2}a})$.

If the function $T$ is increasing, then the condition $n=2^k$ can be dropped

Explanation

If work goes down every layer $⟹$ work of top layer (lower layers become asymptotically negligible)

If work increases every layer $⟹$ work of bottom layer (top layers become asymptotically negligible)

If work stays constant $⟹$ work of all layers (nothing becomes asymptotically negligible)

Tips and Tricks

Sum Formulas

$\sum _{i=1}^{n}i=\frac{n(n+1)}{2}$ and $\sum _{i=1}^n{i}^2=\frac{n(n+1)(2n+1)}{6}$

Integrate (not covered in lectures)

The integral of terms behaves identical to the sum of terms asymptotically, up to constants.

Example ($\sim$ denotes asymptotically equivalent):

$$\begin{array}{rl}\sum _{i=1}^{\lceil \sqrt{n}\rceil }\sqrt{i}& \sim {\int }_1^{\lceil \sqrt{n}\rceil }\sqrt{x}dx\\ & ={\left[\frac{2}{3}{x}^{3/2}\right]}_1^{\lceil \sqrt{n}\rceil }\\ & =\frac{2}{3}(\lceil \sqrt{n}{\rceil }^{3/2}-1)\\ & =\Theta (n^{3/4})\end{array}$$

Integrating logs Asymptotically, every integral of the form $\int \log x=x\log x$.

Multiplication-Subtraction Trick

Works for geometric series.

Example: $T=7^1+7^2+\dots +7^n$

1. Multiply the series by its base:  $7T$
2. Subtract:  $7T-T=7^{n+1}-7^1$ (middle terms cancel)
3. Factor:  $T(7-1)=7^{n+1}-7^1$
4. Divide: $T=\frac{7^{n+1}-7^1}{6}$

If $T$ had constant coefficients, the middle terms would cancel just the same: $7T-T=\alpha 7^{n+1}-\alpha 7^1$, meaning the trick still works.