Week 9 Flashcards
1
Q
What is the recurrence for Merge Sort?
A
T(n) <- 2 x T(n/2) + O(n)
2
Q
What are the two methods to solve recurrences?
A
Unrolling
- Analyse first few levels - Identify pattern - Sum over all levels
- Need no idea about the final answer
Verifying by substitution
- Works if you have a guess
3
Q
What does log(n / 2) equal?
A
log(n/2) = log n - 1
4
Q
What is the geometric series sum?
A
1 + r + … + r^t = (r ^ t+1) - 1 / r - 1
