Introduction / Review
Number of transistors double every two years
This trend has slowed a bit, closer to doubling every 2.5 years
Moore’s Law
Memory: 1 MB
CPU: 2.4 Mhz
First computer
Do you remember how fast the CPU was on your first computer?
How about your current computer? What about your previous computer?
CPU trends
CPU trends
CPU trends
CPU trends
CPU trends
You and your siblings are going to make dinner
How would all three of you make… : (1) turkey?
(2) a salad?
Parallel processing (cooking)
Parallel processing (cooking)
If you make turkey….
preheat
Parallel processing (cooking)
If you make turkey….
preheat
WAIT
Parallel processing (cooking)
If you make turkey….
put in turkey
Parallel processing (cooking)
If you make turkey….
put in turkey
WAIT A LOT
Parallel processing (cooking)
If you make turkey….
take out
Parallel processing (cooking)
If you make turkey….
take out
WAIT
Parallel processing (cooking)
If you make a salad…
chop grate cut
Parallel processing (cooking)
If you make a salad…
chop grate cut
Parallel processing (cooking)
If you make a salad…
dump together
To make use of last 15 years of technology, need to have algorithms like salad
Multiple cooks need to work at the same time to create the end result
Computers these days have 4-8 “cooks” in them, so try not to make turkey
Parallel processing (cooking)
An algorithm is correct if it takes an input and always halts with the correct output.
Many hard problems there is no known correct algorithm and instead approximate algorithms are used
Correctness
What does O(n2) mean? Θ(n2)?
Ω(n2)?
Asymptotic growth
If our algorithm runs in f(n) time, then our algorithm is O(g(n)) means there is an n0 and c such that
0 < f(n) < c g(n) for all n > n0
O(g(n)) can be used for more than run time
Asymptotic growth
f(n)=O(g(n)) means that for large inputs (n), g(n) will not grow slower than f(n)
n = O(n2)? n = O(n)? n2 = O(n)?
Asymptotic growth
f(n)=O(g(n)) gives an upper bound for the growth of f(n)
f(n)=Ω(g(n)) gives a lower bound for the growth of f(n), namely: there is an n0 and c such that
0 < c g(n) < f(n) for all n > n0
Asymptotic growth
f(n)=Θ(g(n)) is defined as:
there is an n0, c1 and c2 such that
0 < c1 g(n) < f(n) < c2 g(n) for all n > n0
Asymptotic growth
Suppose f(n) = 2n2 – 5n + 7 Show f(n) = O(n2):
Asymptotic growth
Suppose f(n) = 2n2 – 5n + 7 Show f(n) = O(n2):
we need to find ‘c’ and ‘n0’ so that
c n2 > 2n2 – 5n + 7, guess c=3
3 n2 > 2n2 – 5n + 7
n2 > – 5n + 7 (RHS is decreasing) so c=3 and n0=2 proves this
Asymptotic growth
Suppose f(n) = 2n2 – 5n + 7 Show f(n) = Ω(n2):
For any general f(n) show: f(n)=Θ(g(n)) if and only if f(n)=O(g(n)) and f(n)=Ω(g(n))
Asymptotic growth
Suppose f(n) = 2n2 – 5n + 7 Show f(n) = Ω(n2):
again we find a ‘c’ and ‘n0’
cn2 < 2n2 – 5n + 7, guess c=1
1 n2 < 2n2 – 5n + 7
0 < n2 -5n +7, or n2 > 5n -7
n > 4, so c=1 and n0=4 proves this
Asymptotic growth
f(n)=Θ(g(n)) implies
f(n)=O(g(n)) and f(n)=Ω(g(n)):
by definition we have ‘c1’, ‘c2’, ‘n0’ so
0 < c1 g(n) < f(n) < c2 g(n) after n0 0 < c1 g(n) < f(n) after n0 is Ω(g(n)) 0 < f(n) < c2 g(n) after n0 is O(g(n))
Asymptotic growth
f(n)=O(g(n)) and f(n)=Ω(g(n)) implies f(n)=Θ(g(n)):
by definition we have c1, c2, n0, n1
Ω(g(n)) is 0 < c1 g(n) < f(n) after n0 O(g(n)) is 0 < f(n) < c2 g(n) after n1 0 < c1 g(n) < f(n) < c2 g(n) after max(n0,n1)
Asymptotic growth
There are also o(g(n)) and w(g(n)) but are rarely used
f(n)=o(g(n)) g(n) grows “much faster” than f(n), specifically:
lim(n→∞) f(n)/g(n) = 0 w(g(n)) is the opposite of o(g(n))
Asymptotic growth
Big-O notation is used very frequently to describe run time of algorithms
It is fairly common to use big-O to bound the worst case and provide empirical evaluation of runtime with data
Asymptotic growth
What is the running time for n (less than 300) people on the following: 1. Does anyone share my birthday? 2. Does any two people share a birthday?
3. Does any two people share a birthday (but I can only remember and ask one date at a time)?
Asymptotic growth
1. O(n) or just n
2. O(n) or just n for small n (https://en.wikipedia.org/wiki/Birth day_problem)
Worst case: 365 (technically 366) Average run time: 24.61659
3. O(n2) or n2
Asymptotic growth
Monotonically increasing means: for all m < n implies f(m) < f(n)
Math review
Monotonically decreasing means: for all m < n implies f(m) > f(n)
Strictly increasing means:
for all m < n implies f(m) < f(n)
In proving it might be useful to use monotonicity of f(n) or d/dn f(n)
Math review
floor/ceiling?
modulus?
exponential rules and definition? logs?
factorials?
Math review
floor is “round down” floor(8/3) = 2
ceiling is “round up”
ceiling(8/3) = 3
(both are monotonically increasing)
Prove: floor(n/2) + ceiling(n/2) = n
Floors and ceilings
Prove: floor(n/2) + ceiling(n/2) = n Case: n is even, n = 2k
floor(2k/2) + ceiling(2k/2) = 2k
k + k = 2k
Case: n is odd, n = 2k+1 floor((2k+1)/2) + ceiling((2k+1)/2) floor(k+1/2) + ceiling(k+1/2)
k + k+1 = 2k + 1
Floors and ceilings
Modulus is the remainder of the quotient a/n:
a mod n = a – n floor(a/n)
7% 2 = 1
Modulus
n! = 1 x 2 x 3 x ... x n 4! = 4 x 3 x 2 x 1 = 24
Guess the order (low to high):
1,000 1,000,000 1,000,000,000 25 210 215 220 230
5! 10! 15! 20!
Factorial
The order is (low to high): {25, 5!, (1,000), 210, 215, (1,000,000), 220, 10!, (1,000,000,000), 230, 15!, 20!} 10! = 3,628,800
15! ≈ 1,307,674,400,000
20! ≈ 2,432,902,000,000,000,000 (210 = 1024 ≈ 1,000 = 103)
Factorial
Find g(n) such that (g(n) ≠ n!): 1. n! = Ω(g(n))
2. n! = O(g(n))
Factorial
1. n! = Ω(g(n))
- n! = Ω(1) is a poor answer - n! = Ω(2n) is decent
2. n! = O(g(n)) - n! = O(nn)
Factorial
(an)m = anm: (23)4 = 84 = 4096 = 212 anam = an+m: 2324 = 8x16 = 128 = 27 a0 = 1
a1 = a
a-1 = 1/a
Exponentials
for all constants: a>1 and b:
What does this mean in big-O notation?
Exponentials
What does this mean in big-O notation?
nb = O(an) for any a>1 and b
i.e. the exponential of anything eventually grows faster than any polynomials
Exponentials
Sometimes useful facts:
ex = sum(i=0 to ∞) xi / i! ex = lim(n → ∞) (1 + x/n)n
Exponentials
Write the first 5 numbers, can you find a pattern:
1. Fi = Fi-1 + 2 with f0 = 0
2. Fi = 2Fi-1 with f0 = 3
3. Fi = Fi-1 + Fi-2, with f0=0 and f1=1
Recurrence relationships
1. Fi = Fi-1 + 2 with f0 = 0
– F0=0, F1=2, F2=4, F3=6, F4=8 – Fi = 2i
2. Fi = 2Fi-1 with f0 = 3
– F0=3, F1=6, F2=12, F3=24, F4=48
– F
i
= 3 x 2i
Recurrence relationships
3. Fi = Fi-1 + Fi-2, with f0=0 and f1=1 – F0=0, F1=1, F2=1, F3=2, F4=3
– F0=5, F1=8, F2=13, F3=21, F4=34
– Fi = [(1+sqrt(5))i–(1-sqrt(5))i]/(2isqrt(5))
Recurrence relationships
3. Fi = Fi-1 + Fi-2 is homogeneous We as Fi = cFi-1 is exponential,
we guess a solution of the form:
Fi = Fi-1 + Fi-2, divide by Fi-2
F2 = F + 1, solve for F
F = (1 ± sqrt(5))/2, so have the form a[(1 + sqrt(5))/2]i+b[(1 – sqrt(5))/2]i
Recurrence relationships
a[(1 + sqrt(5))/2]i+b[(1 – sqrt(5))/2]i with F0=0 and F1=1
2×2 System of equations → solve i=0: a[1] + b[1] = 0 → a = -b
i=1: a[1+sqrt(5)/2] – a[1-sqrt(5)/2]
a[sqrt(5)] = 1 a = 1/sqrt(5) = -b
Recurrence relationships
Fi = 2Fi-1 – Fi-2 , change to exponent Fi = 2Fi-1 – Fi-2 , divide by Fi-2
F2 = 2F – 1 → (F-1)(F-1) = 0
This will have solution of the form: 1i + i x 1i
Recurrence relationships