7 of 58

O(n)

for i = 1 to n� if a < b� a += b��for i = 1 to n� if c < b� c += b

if c < d� c = sqrt(d)

8 of 58

O(n³)

for i = 1 to n� for j = 1 to n� for k = 1 to n� if c < b� c += b�

9 of 58

O(log₂ n)

binarySearch(array, key, low, high): � middle = (low + high) / 2�� if array[middle] == key � return middle

elif key < array[middle]� return binarySearch(array, key, low, middle - 1)

else� return binarySearch(array, key, middle + 1, high)

10 of 58

Binary Search

Find 3 in 1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

1 2 3 4

3 4

�How many times can you halve n (down to 1)? log₂n

11 of 58

Example Graphs

12 of 58

Timings

N = 100 takes 1 second

How long does it take for N = 10000 (100 times more)?

O(log₂n) 2s

O(n) 100s

O(n²) 10,000s (2h:46)

O(n log₂n) 200s

13 of 58

Properties

"Grows no faster than" (Upper bound)
For sufficiently large values
Up to a constant multiplier

O(100n) = O(n)

Fastest growth term only

O(n²+5n+1) = O(n²)

14 of 58

Divide

and

Conquer

15 of 58

Principle

Split problem into sub-problems

Smallest problems could be trivial to solve

Combine results if needed

16 of 58

Binary Search

binarySearch(array, key, low, high): � middle = (low + high) / 2�� if array[middle] == key � return middle

elif key < array[middle]� return binarySearch(array, key, low, middle - 1)

else� return binarySearch(array, key, middle + 1, high)

17 of 58

Merge Sort

mergeSort(array)� first = mergeSort(array[0..n/2])� second = mergeSort(array[n/2..n])

result = []

while first.notEmpty or second.notEmpty� if first[0] < second[0]: smallest = first.removeAt(0)� else: smallest = second.removeAt(0)�� result.add(smallest)

return result

18 of 58

Merge Sort

O(n log₂n)

Why:

max depth is log₂n
at each level n items are merged in total

�Also in general:

T(n) = 2T(n/2) + O(n) gives O(n log₂n)

19 of 58

John Von Neumann

Computing architecture
Linear programming
Game theory
Quantum physics + bomb
Mathematics

20 of 58

D&C - Because

Framework for approaching problems; simplifies work
When done right, reduces run-time

21 of 58

Polynomials

22 of 58

Polynomials

2x² + 5x - 1

x³ - x + 2

a_nxⁿ + a_n-1x^n-1 + … + a₀x⁰

n is the degree

23 of 58

Polynomial Representation

P as coefficients:

[a₀, a₁, a₂, ..., a_n]

24 of 58

Multiplication

(2x² + 5x - 1)(x³ - x + 2) =

2x⁵ - 2x³ + 4x² +

5x⁴ - 5x² + 10x -

x³ + x - 2

= 2x⁵ + 5x⁴ - x³ - x² + 11x - 2

25 of 58

Multiplication Algorithm

r = [0, 0, ...]

for i = 0 to len(a)� for j = 0 to len(b)� r[i + j] += a[i] * b[j]

O(n²)

26 of 58

Alternative Representation

P as values at different points:

[x₁, x₂, ..., x_n+1]

[P(x₁), P(x₂), ..., P(x_n+1)]

27 of 58

Example

P(x) = x² + 1�x in [0, 1, 2]

P(0) = 1�P(1) = 2�P(2) = 5

28 of 58

Multiplication

A(x) = x + 2 A(-1) = 1 A(0) = 2 A(1) = 3

B(x) = x - 1 B(-1) = -2 B(0) = -1 B(1) = 0

C(x) = x² + x - 2 C(-1) = -2 C(0) = -2 C(1) = 0

O(n)

29 of 58

Conversion Between Representation

Evaluation

Given coefficients, compute values at different points

Interpolation

Given values at different points, compute coefficients
Lagrange formula

30 of 58

Idea

Evaluate A and B at 2n+1 points
Multiply the values - O(n)
Interpolate the result to get C

31 of 58

Idea

Evaluate A and B at 2n+1 points - O(n²)
Multiply the values - O(n)
Interpolate the result to get C - O(n²)

Need an Evaluate/Interpolate method faster than O(n²).

32 of 58

Implement Evaluate

We'll try to solve this using D&C.

Evaluate(a, x)

a = [a₀, a₁, ..., a_n]�x = [x₀, x₁, ...]

How to split the problem?

33 of 58

Odd & Even Terms

A [a₀, a₁, a₂, a₃, ...] a₀ + a₁x + a₂x² + a₃x³ + ...

A_even[a₀, a₂, a₄, ...] a₀ + a₂y + a₄y² + ...�A_odd [a₁, a₃, a₅, ...] a₁ + a₃y + a₅y² + ...

34 of 58

Odd & Even Terms

A [a₀, a₁, a₂, a₃, ...] a₀ + a₁x + a₂x² + a₃x³ + ...

A_even[a₀, a₂, a₄, ...] a₀ + a₂y + a₄y² + ...�A_odd [a₁, a₃, a₅, ...] a₁ + a₃y + a₅y² + ...

�A(x) = A_even(x²) + x * A_odd(x²)

�because

a₀ + a₂x² + a₄x⁴ + ... + xa₁+ xa₃x² + xa₅x⁴ + ...

35 of 58

Algorithm Attempt 1

Evaluate(a, x)� a_even = [a₀, a₂, a₄, ...]� a_odd = [a₁, a₃, a₅, ...]� x² = [x₀², x₁², x₂², ...]

v_even = Evaluate(a_even, x²)� v_odd = Evaluate(a_odd, x²)

for i = 0 to len(x)� v[i] = v_even[i] + x[i] * v_odd[i]

return v

36 of 58

Algorithm Attempt 1

Evaluate(a, x)� a_even = [a₀, a₂, a₄, ...]� a_odd = [a₁, a₃, a₅, ...]� x² = [x₀², x₁², x₂², ...]

v_even = Evaluate(a_even, x²)� v_odd = Evaluate(a_odd, x²)

for i = 0 to len(x)� v[i] = v_even[i] + x[i] * v_odd[i]

return v

O(n²)

37 of 58

Positive And Negative Points

x₀, x₁, x₂, ..., x_j, x_j+1, x_j+2, ...

Pick them such as:

x₀ = -x_j�x₁ = -x_j+1�x₂ = -x_j+2�...

38 of 58

Positive And Negative Points

x = 1, 2, 3, 4, ..., -1, -2, -3, -4

x² = 1, 4, 9, 16, ..., 1, 4, 9, 16

39 of 58

Positive And Negative Points

x = 1, 2, 3, 4, ..., -1, -2, -3, -4

x² = 1, 4, 9, 16, ..., 1, 4, 9, 16

also:�

A(x) = A_even(x²) + x * A_odd(x²)

�A(-x) = A_even(x²) - x * A_odd(x²)

40 of 58

Algorithm Attempt 2

Evaluate(a, x)� x_half² = [x₀², x₁², x₂², ..., x_j-1²], j = len(x) / 2

v_even = Evaluate(a_even, x_half²)� v_odd = Evaluate(a_odd, x_half²)

for i = 0 to j� v[i] = v_even[i] + x[i] * v_odd[i]� v[i + j] = v_even[i] - x[i] * v_odd[i]

return v

41 of 58

Algorithm Attempt 2

Evaluate(a, x)� x_half² = [x₀², x₁², x₂², ..., x_j-1²]

v_even = Evaluate(a_even, x_half²)� v_odd = Evaluate(a_odd, x_half²)

for i = 0 to j� v[i] = v_even[i] + x[i] * v_odd[i]� v[i + j] = v_even[i] - x[i] * v_odd[i]

return v

O(nlog₂n)

42 of 58

Ideal Points

Two properties:

the first half are the opposites of the other half

1, 2, 3, 4, -1, -2, -3, -4

the first property holds even after we square half of them

1, 4, 9, 16��

Is this even possible?

43 of 58

Complex Numbers

44 of 58

Basics

-2 -1 1 2

-i

-2i

45 of 58

Basics

z = a + bi

Ex:

2 + 3i

46 of 58

Polar Coordinates

z = r cos θ + i r sin θ

Euler

z = r e^iθ

47 of 58

Polar Coordinates

θ=π

r=1

z = r cos θ + i r sin θ

Euler�

z = r e^iθ

Famous formula

e^iπ = -1

-1

48 of 58

Power

θ=π/4

r=1

Multiplication

z₁ = r₁e^iθ1

z₂ = r₂ e^iθ2

z₁ * z₂ = (r₁r₂)e^i(θ1+θ2)

Raise to power

zⁿ = rⁿe^iθn

Ex:

(e^iπ/4)² = e^iπ/2 = i

49 of 58

Unit Circle

Unit circle

All points with r = 1

50 of 58

Roots OF unity

zⁿ = 1

z⁸ = 1 has 8 solutions

ω₈⁰, ω₈¹, ω₈², ω₈³,...

ω₈¹ can simply be written ω₈ since the others are just its powers

Property - half are opposites

51 of 58

Roots OF unity

Property - the squares of ω₈ values are the ω₄ values

52 of 58

Roots OF unity

Property - the squares of ω₈ values are the ω₄ values

(ω_n)² = ω_n/2

Property - half of these are still opposites

Bingo!

53 of 58

Wrapping Up

54 of 58

Evaluate

w_d is the first d root of unity; d is the smallest power of 2 larger than the degree of a

Evaluate(a, w_d)� if len(a) = 1 return a� v_even = Evaluate(a_even, w_d²)� v_odd = Evaluate(a_odd, w_d²)

for i = 0 to j� v[i] = v_even[i] + w_dⁱ * v_odd[i]� v[i + j] = v_even[i] - w_dⁱ * v_odd[i]

return v

55 of 58

Interpolate

V = Evaluate(a, w_d)

we can get a back simply doing

a = 1/d Evaluate(V, w_d^d-1)

56 of 58

Polynomial Multiplication

Multiply(a, b)

Va = Evaluate(a, w_d)� Vb = Evaluate(b, w_d)� � for i = 0 to len(Va)� Vc = Va[i] * Vb[i]� � c = 1/d * Evaluate(Vc, w_d^d-1)� return c

O(nlog₂n)

1 of 58

2 of 58

3 of 58

4 of 58

5 of 58

6 of 58

7 of 58

8 of 58

9 of 58

10 of 58

11 of 58

12 of 58

13 of 58

14 of 58

15 of 58

16 of 58

17 of 58

18 of 58

19 of 58

20 of 58

21 of 58

22 of 58

23 of 58

24 of 58

25 of 58

26 of 58

27 of 58

28 of 58

29 of 58

30 of 58

31 of 58

32 of 58

33 of 58

34 of 58

35 of 58

36 of 58

37 of 58

38 of 58

39 of 58

40 of 58

41 of 58

42 of 58

43 of 58

44 of 58

45 of 58

46 of 58

47 of 58

48 of 58

49 of 58

50 of 58

51 of 58

52 of 58

53 of 58

54 of 58

55 of 58

56 of 58

57 of 58

58 of 58