Standard 6: Divide and Conquer 3: Recurrences

Short description: Analyze novel D&C algorithms; write down recurrences and their solutions.

Relevant notes: Topic B: Divide and Conquer.

Full description

Given a Divide and Conquer algorithm, write down a recurrence for the runtime and solve it using the master theorem. The master theorem will be given in the problem statement.

Example problem

Write a recurrence for the runtime $T(n)$ of the following algorithm. Briefly show your work. Then, solve the recurrence using the master theorem.


1  strange_sum(A):
2      let n = len(A)
3      if n == 1:
4          return A[0]
5      x = strange_sum(A[0:n/2])
6      y = strange_sum(A[n/4:3*n/4])
7      z = strange_sum(A[n/2:end])
8    

9      my_max = 0
10     for i = 0 to len(A)-1:
11       if A[i] > my_max:
12         my_max = A[i]
13     return x + y + z + my_max

Master theorem: If an algorithm satisfies the recurrence $T(n) = m T(n/k) + O(n^c)$, then its time complexity is:

$O(n^c)$ if $c > \log_k(m)$; or
$O(n^{\log_k(m)})$ if $c < \log_k(m)$; or
$O(n^c \log(n))$ if $c = \log_k(m)$.

Sample solution

Sample solution.

For big-O, we can pretend that each line that takes a constant number of steps takes 1 step. We recursively call strange_sum on arrays of length n/2, three times.


1 strange_sum(A):                     // T(n) total
2     let n = len(A)                  // 1
3     if n == 1:                      // 1
4         return A[0]                 // 1
5     x = strange_sum(A[0:n/2])       // T(n/2)
6     y = strange_sum(A[n/4:3*n/4])   // T(n/2)
7     z = strange_sum(A[n/2:end])     // T(n/2)


1     my_max = 0                      // 1
2     for i = 0 to len(A)-1:          // 1 per loop
3       if A[i] > my_max:             // 1 per loop
4         my_max = A[i]               // 1 per loop
5     return x + y + z + my_max       // 1

The loop executes n times, and takes 3 steps per loop. So the recurrence is

\begin{align*} T(n) &= 3 T(n/2) + 3n + 5 \\ &= 3 T(n/2) + O(n) . \end{align*}

In the master theorem, we have $k=2$, $m=3$, and $c=1$. Then $\log_k(m) = \log_2(3) > 1$. So we are in the second case, and the time complexity is $O(n^{\log_2(3)})$.

Rubric

Rubric.

To pass, a solution must follow the course requirements for writing and proofs.

To pass, the solution must both state the correct recurrence $T(n) = 3T(n/2) + O(n)$ and correctly apply the master theorem to solve it and get $O(n^{\log_2(3)})$.

In addition, the solution should adequately explain how to obtain the recurrence by briefly analyzing the pseudocode. It should briefly explain how the master theorem applies in this specific case, i.e. what the parameters are and which case of the master theorem applies.

The numerical rubric for this problem is:

4 (Pass, Near-Perfect): correct, clear, and with brief explanations.
3 (Pass, Proficient): correct recurrence and time complexity; mostly clear explanations of how to obtain the recurrence by analyzing the code, though some hand-waving and brevity is allowed if the key points of $3T(n/2)$ and $O(n)$ are explained. Mostly-clear explanation of how the master theorem applies. Does not contain much excess writing.
2 (Fail, Progress): may give an incorrect recurrence or time complexity, but uses a correct general approach to analyze the time complexity and to apply the master theorem. May not explain how an answer is arrived at or give an explanation that does not fit with the given answer.
1 (Fail, Wrong Track): May give a recurrence in a wrong format or with unclear relationship to the code. May not apply the master theorem or may mis-apply it.