May 13th

Complexity Theory Basics

When analyzing algorithms we want to reason (quickly) about the running time of algorithms. We use the RAM model in which the following are considered to cost 1 CPU operation:

• Addition or subtraction of two numbers
• Multiplication of two numbers
• Comparison of two numbers
• A function call
• An if statement
• Any memory access

Other attributes:

• Memory is unlimited
• Recursive calls, for loops, and while loops all require analysis

The goal is to allow you to count operations and CPU cost without needing to know the specific architecture you are running on.

Some notes on algorithm analysis.

Big-Oh Analysis

Big-oh, $$\mathcal{O}( \cdot )$$, has nothing to do with CPU cost, persay, it is just a way to fuzzily compare functions. We say that $$f(n) = \mathcal{O}(g(n))$$ if and only if there is some cutoff $$N$$ and positive real $$c$$ such that for all $$n \geq N$$ we have $$|f(n)| \leq c \cdot |g(n)|$$.

The official definition is there to get you out of trouble when you feel lost, but it seems way more complicated than it really is. It's really used to compare functions.

Intro Problems

1. Prove, using the definition, that $$3n^2 = \mathcal{O}(n^2)$$.
2. Do the same to show that $$\frac{1}{5} n = \mathcal{O}(n^3)$$.
3. Show that $$2^n \neq \mathcal{O}(n^4)$$

Properties of $$\mathcal{O}$$

For $$f, g, f_1, g_1$$ functions from $$\mathbb{N} \to \mathbb{R}$$ we know that:

1. If $$f = \mathcal{O}(g)$$ then $$f + g = \mathcal{O}(g)$$
2. If $$f = \mathcal{O}(f_1)$$ and $$g = \mathcal{O}(g_1)$$ then $$f \cdot g = \mathcal{O}(f_1 \cdot g_1)$$
3. $$c \cdot f = \mathcal{O}(f)$$ for any constant real $$c$$
Upshot is that you pretty much ignore small terms.

Next batch

1. Prove that $$a_n x^n + \cdots + a_0 = \mathcal{O}(x^n)$$
2. For $$b \geq a$$ prove that $$n^a = \mathcal{O}(n^b)$$.
3. More problems to practice with here

Putting it all together

So to use big-oh in algorithms we ballpark the cost of loops and multiplications ignoring specific details.

Sample algorithms to practice on: sorting!

This is insert sort done via Folk Dance!

or a gif: 1. What is the best input for this algorithm?
2. What is the worst input for this algorithm?
3. Analyze the number of comparisons in insertion sort for the worst-case on $$n$$ items.