Studio 4: Solving Recurrences

Part A: Solving Recurrences by Substitution

Our new computer science building has a very fancy system for controlling its lighting. There are numerous light fixtures, all of which are controlled by a row of $n$ switches in the department chair's office. Each switch can be either "on" or "off". Here's an example with $n=3$ switches:

switch panel

However, switches do not control individual fixtures: the state of each fixture -- lit or unlit -- is a complex Boolean function of all $n$ switches. (Hey, it's a CS building -- what did you expect?)

Being environmentally conscious, you want to know if it's possible to turn off all the lights in the building at once. To do this, you proceed recursively as follows:

  1. Flip the first switch to "on", if it is not yet on.
  2. Determine if any setting of the remaining $n-1$ switches turns off all the lights.
  3. Flip the first switch to "off".
  4. Determine if any setting of the remaining $n-1$ switches turns off all the lights.

Question A1: Write a recurrence describing the maximum number of flips $F(n)$ you might need to find a setting, if any, that turns off all the lights using the above procedure.

Question A2: Intuitively, how fast do you think the number of flips grows as a function of $n$? Why?

Question A3: Use substitution followed by an inductive proof to characterize the asymptotic behavior of $F(n)$ with a $\Theta$ bound.

Part B: Solving Recurrences Using Recursion Trees

For each of the following examples, use the recursion tree methodology to figure out the asymptotic running time of the algorithm described. In each case, you should

  • write a recurrence that describes the algorithm's running time $T(n)$;

  • sketch the recursion tree;

  • fill in a table like that shown below to account for the work of the algorithm;

  • using the tree and table, compute a closed-form asymptotic complexity (a $\Theta$ bound) for the algorithm.

If the recurrence includes terms of the form $T\left( \frac{n}{b} \right)$, you may assume that $n$ is a power of $b$, so that $n/b$ will always be an integer for $n > 1$. Assume that $T(1) = d$ for some fixed constant $d$.

Here's an example table for $T(n) = T(n-1) + 10$:

Depth Problem Size #Nodes Work Per Node Total Work
0 $n$ 1 10 10
1 $n-1$ 1 10 10
2 $n-2$ 1 10 10
$i$ $n-i$ 1 10 10
$n-1$ 1 1 10 10

Question B1: Given a problem of size $n$, this algorithm spends linear time scanning an array of size $n$, then makes three recursive calls each on arrays of size $n/3$, then spends linear time merging the results.

Question B2: Given a problem of size $n$, this algorithm makes four recursive calls on problems of size $n/2$. Other than these recursive calls, the algorithm spends $2n$ time.

Question B3: Given a problem of size $n$, this algorithm makes one recursive call on a problem of size $n/2$. Other than this recursive call, the algorithm executes $n^3$ ticks.

Part C: Imprecisely Stated Recurrences

When you see running-time recurrences written in the literature, you will often see them written imprecisely. For example, you might see the running time of an algorithm quoted as \[ T(n) = 2T(n/2) + \Theta(n) . \] This example specifies neither the base case of the recurrence nor the constant in its non-recursive term. Does it give us enough information to solve the recurrence?

  • Open the Excel file recurrence.xlsx in the studio4 directory.

You will see a spreadsheet with three columns. The first column gives input sizes $n$; for simplicity, we list only successive powers of 2 rather than all possible $n$. The second column computes the value of the recurrence $T(n) = 2T(n/2) + n$, with base case $T(1) = 1$. The third column is simply the ratio $T(n)/n$.

  • Plot the ratio $T(n)/n$ as a function of $n$.

Question C1: What asymptotic solution does your plot suggest for this recurrence as a function of $n$?

Hint: to make the plot easier to understand, try making the x-axis a logarithmic scale. Click on the axis, and you should get a pane with options including a "Logarithmic scale" check-box.

Now, let's play around with the recurrence and see what happens to its rate of growth.

  • Change the base-case value $T(1)$ from 1 to some larger values.

Question C2: Does the asymptotic behavior of the recurrence change if you change the base-case value? Can you justify your answer analytically?

  • Now change the constant factor in front of the non-recursive term.

    In cell B3, add a multiplicative constant other than 1 in front of the last term $A3 in the formula. For example, you could say 2*$A3. Then, cut and paste the modified formula into all rows of the table.

Question C3: Does the asymptotic behavior of the recurrence change now? Can you justify your answer analytically?

Finally, suppose that we change the base case so that instead of having $T(1) = 1$, we have $T(n_0) = 1$ for some constant $n_0 > 1$. This change effectively "chops off" the bottom of the recursion tree.

  • To change $n_0$ for the base case, select a row of the table, corresponding to $n_0$, and set the recurrence value in that row to 1. Try a few different choices for $n_0$.

Question C4: Does the asymptotic behavior of the recurrence change for $n \geq n_0$? Can you justify your answer analytically?

Question C5: Why might we report running-time recurrences like the one shown above imprecisely, omitting the constant on the non-recursive term and skipping the base case entirely?