Chapter 3: Analyzing Recursive Code

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/17

encourage image

There's no tags or description

Looks like no tags are added yet.

18 Terms

1
New cards
[Ch 3] Recursion that halves the input each call: example and runtime?
Binary search, O(log n).
2
New cards
[Ch 3] Recursion that splits the input and does linear work at each level: example and runtime?
Merge sort, O(n log n).
3
New cards
[Ch 3] Recursion where each call makes two more calls: example and runtime?
Naive Fibonacci, O(2ⁿ).
4
New cards
[Ch 3] Recurrence relation
An equation that defines each term from earlier terms. Used to describe the runtime of recursive code.
5
New cards
[Ch 3] Master Theorem
A shortcut for solving recurrences of the form T(n) = a·T(n/b) + Θ(nᶜ).
6
New cards
[Ch 3] Master Theorem: what do a, b, and c represent?
a = number of recursive calls. b = how much the input shrinks each call. nᶜ = work done outside the recursive calls.
7
New cards
[Ch 3] Master Theorem: what are the three cases?
log_b(a) < c → Θ(nᶜ). log_b(a) = c → Θ(nᶜ log n). log_b(a) > c → Θ(n^(log_b a)).
8
New cards
[Ch 3] Binary search: recurrence and solution?
T(n) = T(n/2) + Θ(1), which solves to Θ(log n).
9
New cards
[Ch 3] Merge sort: recurrence and solution?
T(n) = 2T(n/2) + Θ(n), which solves to Θ(n log n).
10
New cards
[Ch 3] Binary search: what must be true of the input array?
It must be sorted.
11
New cards
[Ch 3] binary_search(): what is the "not found" base case?
`if low > high: return -1`
12
New cards
[Ch 3] binary_search(): how is the midpoint calculated?
`mid = low + (high - low) // 2`
13
New cards
[Ch 3] binary_search(): why `//` instead of `/`?
`/` always returns a float, which can't be used as a list index. `//` does integer division.
14
New cards
[Ch 3] binary_search(): is integer overflow a concern in Python?
No, Python ints never overflow. `low + (high - low) // 2` is the standard form because (low + high) / 2 can overflow in languages like Java.
15
New cards
[Ch 3] binary_search(): what is the "found" base case?
`if arr[mid] == target: return mid`
16
New cards
[Ch 3] binary_search(): what is the recursive call when arr[mid] > target?
`return binary_search(arr, target, low, mid - 1)` searches the left half.
17
New cards
[Ch 3] Code: write the full recursive binary search.
```python
def binary_search(arr, target, low, high):
if low > high:
return -1 # Base case: not found

mid = low + (high - low) // 2

if arr[mid] == target:
return mid # Base case: found
elif arr[mid] > target:
return binary_search(arr, target, low, mid - 1) # Recurse left
else:
return binary_search(arr, target, mid + 1, high) # Recurse right
```
18
New cards
[Ch 3] binary_search(): what is the recursive call when arr[mid] < target?
`return binary_search(arr, target, mid + 1, high)` searches the right ha