Divide and Conquer

Question 1

Q: If a recursive algorithm divides its input size by 2 at each step, follows one path, and does constant work, what’s the runtime?

Answer 1

A: O(log n) - Example: Binary Search

Master Theorem:
T(n) = aT(n/b) + O(n^d)
T(n) =1T(n/2) + O(n^0) # Each level is O(1)
b^d (1) = a (1), therefore O(n^d log n) using MT
Simplifies to O(log n)

Question 2

Q: If a recursive algorithm looks at BOTH halves of the input and does constant work per level, what’s the runtime?

Answer 2

A: O(n) - Example: Binary Tree Traversal

Master Theorem:
T(n) = aT(n/b) + O(n^d)
T(n) = 2T(n/2) + O(n^0)
- subproblems: 2
- scaling: 2
- work at each level: O(1)
b^d (1) < a (2), therefore O(n^{log_b a}) using MT
Plug in: O(n^{log_2 2})
Simplifies to O(n^1) to O(n)

Question 3

Q: If a recursive algorithm divides input by 4, looks at all quarters, and does O(n^2) work per level, what’s the runtime?

Answer 3

A: O(n^2)

Question 4

Q: If a recursive algorithm divides input by 2, processes both halves, and does O(n*log(n)) work per level, what’s the runtime?

Answer 4

A: O(n*log^2(n))

Question 5

Q: If a recursive algorithm divides input by 3, processes all thirds, and does O(sqrt(n)) work per level, what’s the runtime?

Answer 5

A: O(n^{log_3(3)}) = O(n)

Question 6

Q: If a recursive algorithm divides input by 2, processes all halves, and does O(n^2) work per level, what’s the runtime?

Answer 6

A: O(n^2*log(n))

Question 7

Q: If a recursive algorithm divides input into 3 equal parts, processes all parts, and does O(1) work per level, what’s the runtime?

Answer 7

A: O(n^{log_3(3)}) = O(n)

Question 8

Q: If a recursive algorithm divides input by 2, looks at BOTH halves, and does O(n) work per level, what’s the runtime?

Answer 8

A: O(n log n) - Example: Mergesort

Question 9

Q: When you see T(n) = 1T(n/2) + O(n^0), what runtime should you expect?

Answer 9

A: O(log n)

Why? Dividing by 2 each time with constant work per level

Master theorem:
b^d = 2^0 = 1 = a
if b^d = a, T(n) = O(n^d log n)
(simplifies to O(log n) since d is zero)

Question 10

Q: When you see T(n) = 2T(n/2) + O(n), what runtime should you expect?

Answer 10

A: O(n log n)

Why? Linear work at each level, with log n levels

Master theorem:
b^d = 2 = a, so
T(n) = O(n log n)

Question 11

Q: When you see T(n) = 2T(n/2) + O(1), what runtime should you expect?

Answer 11

A: O(n)

Why? Even though dividing by 2, visiting both halves means visiting all n elements once

Master’s Theorem:
b^d = 2^0 = 1
2 (a) > 1 (b^d)

if a > b^d: O(n^{log_b a})
T(n) = O(n^{log_2 2})
= O(n^1)
= O(n)

Question 12

Q: If a recursive algorithm divides input into 3 parts and does constant work, what’s the runtime?

Answer 12

A: O(log_3 n)
Why? Number of times you can divide n by 3 until reaching 1

Question 13

Given O(3^(log_2 n)) , solve for n

(Hint: just need to swap 2 things)

Answer 13

O(n^(log_2 3))

Idea: Switch 3 and n

Question 14

[FastSelect] Explain why select v in list A between 25th and 75th percentile will ensure sublists A_L and A_R to have size at worst 3/4 of A

Answer 14

1. A number at the 75th percentile has 75% of elements less than or equal to it, and 25% greater. A_L has at most 75% of elements
2. A number at the 25th percentile has 25% of elements less than or equal to it, and 75% greater A_R has at most 75% of elements.
3. Therefore, no matter where v falls in this range, neither S_L nor S_R can be larger than 75% of the original array

Question 15

[Masters Theorem]
What does n^{log_b a} represent in a subproblem of size n/b?

Answer 15

Width of the last level (base case of 1)

Question 16

Master’s Theorem formula:
if a > b^d, what is T(n)?

Answer 16

O(n^{log_b a})

Question 17

Master’s Theorem formula:
if a = b^d, what is T(n)?

Answer 17

O(n^d log(n))

Question 18

Master’s Theorem formula:
if a < b^d, what is T(n)?

Answer 18

O(n^d)

Question 19

[Masters Theorem]
What does log_b n represent given subproblems of size n/b?

Answer 19

The depth of the subproblems

Question 20

Observe the substitution method when solving runtime of Fast Integer Mult without Master Theorem:
$$
T(n) <= cn (1 + (3/2) + (3/2)^2 + … + (3/2)^{i-1}) + 3^i T(n/2^i)
$$
When solving for base case, we let i = log_2(n).

Q: Why do we use base of 2 for this problem?

Answer 20

The base of i comes from the scaling factor of the recurrence relation, which is n/2

Question 22

Manipulate this polynomial for n:
4^{log_2 n}

Answer 22

n^2

Question 23

Manipulate this polynomial for n:
3^{log_2 n}

Answer 23

n^{log_2 3}

Question 24

Geometric Series:

Given a geo-series:
\sum_{j=0}^k a^j = 1 + a + a^2 + … + a^k

If a>1, what is Big-O?

Answer 24

O(a^k)

(last term dominates)

Question 25

Geometric Series:

Given a geo-series:
\sum_{j=0}^k a^j = 1 + a + a^2 + … + a^k

If a=1, what is Big-O?

Answer 25

O(k)

(each term is exactly 1, number of terms is O(k+1) which is O(k)

Question 26

Geometric Series:

Given a geo-series:
\sum_{j=0}^k a^j = 1 + a + a^2 + … + a^k

If a<1, what is Big-O?

Answer 26

O(1)

(each term is decreasing, so dominant term is O(1))