Divide-and-conquer

Question 1

What’s the recurrence relation and bigO time of the simple divide-and-conque for polynomial Multiplication

Answer 1

T(n) = 4T(n/2) + O(n)

T(n) = O(n²)

Question 2

What’s the recurrence relation and bigO time of the Gauss’s trick for polynomial Multiplication

Answer 2

T(n) = 3T(n/2) + O(n)

T(n) = O(n^log₂3)

Question 3

Master theorem. a/b^d >1. What’s big O

Answer 3

O(n^log_ba)

Question 4

Master theorem. a/b^d <1. What’s big O

Answer 4

O(n^d)

Question 5

Master theorem. a/b^d =1. What’s big O

Answer 5

O(n^dlogn)

Question 6

Binary search can only apply to sorted arrays?

Answer 6

Yes

Question 7

What’s the recurrence of Binary search and what’s bigO time

Answer 7

T(n) = T(n/2)+O(1)

O(logn)

Question 8

What’s the recurrence of Mergesort and what’s bigO time?

Answer 8

T(n) = 2T(n/2) + O(n)

O(nlogn)

Question 9

Mergesort psedo-code

Answer 9

Question 10

Is mergesort optimal?

Answer 10

Yes.

Consider any such tree that sorts an array of n elements. Each of its leaves is labeled by a permutation of {1, 2, … , n}. In fact, every permutation must appear as the label of a leaf. The reason is simple: if a particular permutation is missing, what happens if we feed the algorithm an input ordered according to this same permutation? And since there are n! permutations of n elements, it follows that the tree has at least n! leaves.

This is a binary tree, and we argued that it has at least n! leaves. Recall now that a binary tree of depth d has at most 2^d leaves (proof: an easy induction on d). So, the depth of our tree–and the complexity of our algorithm–must be at least log(n!). And it is well known that log(n!)  >= c*n*log n for some c > 0.

We have established that any comparison tree that sorts n elements must make, in the worst case, (n log n) comparisons, and hence mergesort is optimal!

Question 11

expected average and worst time of finding medium with good pivot?

Answer 11

T(n) <= T(3n/4) + O(n)

average time: O(n)

Worst time: O(n²)

Question 12

expected average and worst time of quicksort

Answer 12

average time O(n logn)

worst time O(n²)

Question 13

pseudo-code for finding good pivot and medium

Answer 13

Question 14

BigO time for simpy matrix multiplication

Answer 14

O(n³)

Question 15

what’s the Inversion formula of FFT coefficient matrix M_n(w)^-1?

Answer 15

M_n(w)^-1 = 1/n*M_n(w^-1)

Question 16

pseudo-code for The fast Fourier transform

Answer 16

Question 17

Why The columns of matrix M_n(w) are orthogonal to each other?

Answer 17

Question 18

running time for FFT?

Answer 18

T(n) = 2T(n/2) + O(n)

O(n log n)

Question 19

pseudo-code for merge function in mergesort

Answer 19