Analyzing Algorithms part 2
Andy Novocin
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
Suppose you can reliably perform \(10^9\) operations per second
e.g. My laptop: 1.6GHz Dual Core so 3.2 Giga FLOPS
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}}\) |
Traveling Salesman Problem
You have a route of \( n \) cities
Find shortest cycle
which visits all of them
and gets you home
Brute Force Solution?
Takes \( \mathcal{O}(n!) \)
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]);
}
Count the worst-case swaps.
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}) \)
Challenge 2
Grab a book, open to page 730 (last page)
Count the number of pages you see as you:
Tell me what the Miller-Rabin algorithm does?
Dividing, Doubling, and Logs
Binary Search
Finding a name in the phone book:
Takes \( \mathcal{O}(\log{n}) \) page turns.
Why \( \log{n} \)?
Recall that \( b^p = x \iff \log_{b}{x} = p \)
When there is repeated doubling, after \(i\) iterations the total is \( n = 2^i\).
So \( \log{ n } = i \), in other words: \( \log{} \) counts the iterations.
\(L_i\) has \( 2^i \) nodes and \( \log{n} \) is the height
Properties of Logs
\( \log{xy} = \log{x} + \log{y} \)
\( \log_{b}{x} = \frac{\log_{k}{x}}{\log_{k}{b}} \)
\( \log_b{x^c} = c \log_n{x} \)
For most of our purposes the base will not matter
Divide and Conquer
Can you split your problem into halves?
If so then there will be \( \log{n} \) splits.
Repeated squares
Merge Sort (more later)
Some useful sums
\( \sum_{i=0}^n b^i = \frac{b^{n+1} - 1}{b - 1} = \mathcal{O}(b^n) \)
\( \sum_{i=1}^{n} \frac{1}{i} \approx \ln{n} \)
\( \sum_{i=1}^n \log {i} = \log{n!} = \Theta (n \log{n}) \)
Andy's secret \( (1 + \Delta)^n \) method (if there is time)