Analysing loops and recurrences
Going from code to its cost by calculation: number of iterations of dependent loops, the recurrence of a recursive algorithm, the recursion tree, the master theorem and amortised cost.
- 26 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
Cost recurrence: what is it?
Show the answer
An equation that expresses the cost of a recursive algorithm on an input of size n using its cost on smaller inputs.
Merge sort gives T(n) = 2T(n/2) + n: two calls on half the input, plus linear work to merge. You write it down by reading the code, then solve it.
Which recurrence describes the cost of this function?
```python
def chercher(t, x, lo, hi):
if lo >= hi:
return -1
m = (lo + hi) // 2
if t[m] == x:
return m
if t[m] < x:
return chercher(t, x, m + 1, hi)
return chercher(t, x, lo, m)`T(n) = T(n/2) + 1T(n) = 2T(n/2) + 1T(n) = T(n - 1) + 1T(n) = T(n/2) + n
Show the answer
T(n) = T(n/2) + 1Only one recursive call runs, on half the cells, with constant work (one midpoint and two comparisons). The two calls written in the code never run together. Result: O(log n).
In T(n) = aT(n/b) + f(n), the master theorem compares f(n) with …, the combined cost of the tree's ….
Show the answer
In T(n) = aT(n/b) + f(n), the master theorem compares f(n) with n^(log_b a), the combined cost of the tree's leaves.
The tree has log_b n levels and a^(log_b n) = n^(log_b a) leaves. For 4T(n/2) + n, compare n with n²: the leaves dominate and T(n) = Θ(n²).
Divide and conquer: what is it?
Show the answer
A method that splits a problem into smaller subproblems of the same kind, solves them recursively, then combines their results.
The cost comes from three things: the number of subproblems a, their size n/b and the work of splitting and combining f(n). The recurrence T(n) = aT(n/b) + f(n) gathers them.