## Daily Problem:

#### Find $$c \geq 0$$ such that $$f(n) \leq c \cdot g(n)$$ for all $$n \geq 2$$:

• $$f(n) = n^2 + n + 1, g(n) = 2n^3$$
• $$f(n) = n \sqrt{n} + n^2, g(n)= n^2$$
• $$f(n) = n^2 - n + 1, g(n)= \frac{n^2}{2}$$

## Families of functions

• $$\log{n} = o(\sqrt{n})$$
• $$\sqrt{n} = o(n)$$
• $$n = o(n\log{n})$$
• $$n\log{n} = o(n\sqrt{n})$$
• $$n\sqrt{n} = o(n^2)$$
• $$n^2 = o(n^3)$$
• $$n^k = o(2^n)$$ for fixed $$k$$
• $$2^n = o(n!)$$
• $$n! = o(n^n)$$
• $$n^n = o(2^{2^n})$$

## Largest Attackable Problem

#### If you've designed an algorithm which uses $$2^n$$ operations

• Run for 1 hour to solve a problem of size $$n = 41$$
• Run for 1 year to solve when $$n = 54$$
• Run for 31 years to solve when $$n = 59$$
• Run since Big Bang and you can solve a problem of size $$n = 88$$

## Largest Attackable Problem

#### If you've designed an algorithm which uses $$n^2$$ operations:

• Run for 1 hour to solve a problem of size $$n$$ is 1 million
• Run for 1 year to solve when $$n$$ is 100 million
• Run for 31 years to solve when $$n$$ is half a billion
• Run since Big Bang and you can solve a problem of size 17.5 trillion
SoU 1 Second 1 Minute 1 Hour 1 Day 1 Year My Lifetime All of time
$$n^n$$ 9 10 11 12 14 15 20
$$n!$$ 12 13 15 16 18 19 26
$$2^n$$ 29 35 41 46 54 59 88
$$n^{14}$$ 4 5 7 9 15 19 80
$$n^{10}$$ 7 11 18 24 44 62 461
$$n^7$$ 19 34 62 97 227 371 6400
$$n^3$$ 512 $$2.05 \cdot 10^{3}$$ $$8.19 \cdot 10^{3}$$ $$3.28 \cdot 10^{4}$$ $$2.62 \cdot 10^{5}$$ $$5.24 \cdot 10^{5}$$ $$5.37 \cdot 10^{8}$$
$$n^2$$ $$1.64 \cdot 10^{4}$$ $$1.31 \cdot 10^{5}$$ $$1.05 \cdot 10^{6}$$ $$8.39 \cdot 10^{6}$$ $$1.34 \cdot 10^{8}$$ $$5.37 \cdot 10^{8}$$ $$1.76 \cdot 10^{13}$$
$$n\sqrt{n}$$ $$5.24 \cdot 10^{5}$$ $$8.39 \cdot 10^{6}$$ $$1.34 \cdot 10^{8}$$ $$1.07 \cdot 10^{9}$$ $$6.87 \cdot 10^{10}$$ $$5.50 \cdot 10^{11}$$ $$5.76 \cdot 10^{17}$$
$$n\log(n)$$ $$6.71 \cdot 10^{7}$$ $$4.29 \cdot 10^{9}$$ $$2.75 \cdot 10^{11}$$ $$4.40 \cdot 10^{12}$$ $$1.13 \cdot 10^{15}$$ $$3.60 \cdot 10^{16}$$ $$9.67 \cdot 10^{24}$$
$$n$$ $$1.00 \cdot 10^{9}$$ $$6.00 \cdot 10^{10}$$ $$3.60 \cdot 10^{12}$$ $$8.64 \cdot 10^{13}$$ $$3.15 \cdot 10^{16}$$ $$9.78 \cdot 10^{17}$$ $$4.42 \cdot 10^{26}$$
$$\sqrt{n}$$ $$1.00 \cdot 10^{18}$$ $$3.60 \cdot 10^{21}$$ $$1.30 \cdot 10^{25}$$ $$7.46 \cdot 10^{27}$$ $$9.95 \cdot 10^{32}$$ $$9.56 \cdot 10^{35}$$ $$1.95 \cdot 10^{53}$$
$$\log{n}$$ $$\geq 10^{10^{9}}$$ $$\geq 10^{10^{10}}$$ $$\geq 10^{10^{12}}$$ $$\geq 10^{10^{13}}$$ $$\geq 10^{10^{16}}$$ $$\geq 10^{10^{17}}$$ $$\geq 10^{10^{26}}$$

## Selection Sort

for (i = 0; i < n; i++){
min = i;
for (j=i+1; j < n; j++)
if (s[j] < s[min]) min=j;
swap(s[i], s[min]);
}

## Stretch, find partner, solve

#### 2-21 True of False:

• $$2n^2 + 1 = \mathcal{O}(n^2)$$
• $$\sqrt{n} = \mathcal{O}(\log{n})$$
• $$\log{n} = \mathcal{O}(\sqrt{n})$$
• $$n^2(1+\sqrt{n}) = \mathcal{O}(n^2 \log{n})$$
• $$3n^2 + \sqrt{n} = \mathcal{O}(n^2)$$
• $$\sqrt{n} \log{n} = \mathcal{O}(n)$$
• $$\log{n} = \mathcal{O}(n^{-1/2})$$