Problem Set 2

Suppose the running time of an algorithm is governed by the recurrence \(T(n) = 7 * T(\frac{n}{3}) + n^2\). What’s the overall asymptotic running time (i.e., the value of \(T(n)\))?

• \(\Theta(n^{2.81})\)
• \(\Theta(n^2)\)
• \(\Theta(n^2\log n)\)
• \(\Theta(n\log n)\)

ANSWER: Applying the Master Method, \(a = 7, b = 3, d = 2, a < b^d\), case 2, work done at the root dominates the running time, therefore, running time is \(\Theta(n^2)\). Option 2 is correct.

Suppose the running time of an algorithm is governed by the recurrence \(T(n) = 9 * T(\frac{n}{3}) + n^2\). What’s the overall asymptotic running time (i.e., the value of \(T(n)\))?

• \(\Theta(n^{3.17})\)
• \(\Theta(n^2\log n)\)
• \(\Theta(n^2)\)
• \(\Theta(n\log n)\)

ANSWER: Applying the Master Method, \(a = 9, b = 3, d = 2, a = b^d\), work done at every level is the same, case 1, therefore, running time is \(\Theta(n^2\log n)\). Option 2 is correct.

Suppose the running time of an algorithm is governed by the recurrence \(T(n) = 5 * T(\frac{n}{3}) + 4n\). What’s the overall asymptotic running time (i.e., the value of \(T(n)\))?

• \(\Theta(n^{\frac{\log 3}{\log 5}})\)
• \(\Theta(n^{\log_3 5})\)
• \(\Theta(n^{\frac{5}{3}})\)
• \(\Theta(n^{2.59})\)
• \(\Theta(n^2)\)
• \(\Theta(n\log n)\)

ANSWER: Applying the Master Method, \(a = 5, b = 3, d = 1, a > b^d\), work done = number of leaves, case 3, therefore, running time is \(\Theta(5^{\log_3 n}) = \Theta(n^{\log_3 5})\). Option 2 is correct.

Consider the following pseudocode for calculating \(a^b\) (where \(a\) and \(b\) are positive integers)

FastPower(a,b) :
  if b = 1
    return a
  else
    c := a*a
    ans := FastPower(c,[b/2])
  if b is odd
    return a*ans
  else return ans
end

Here \([x]\) denotes the floor function, that is, the largest integer less than or equal to \(x\).

Now assuming that you use a calculator that supports multiplication and division (i.e., you can do multiplications and divisions in constant time), what would be the overall asymptotic running time of the above algorithm (as a function of \(b\))?

• \(\Theta(\log b)\)
• \(\Theta(\sqrt{b})\)
• \(\Theta(b\log b)\)
• \(\Theta(b)\)

ANSWER: Outside of recursion, we do constant work; each time, the input size is halved, therefore, \(a = 1, b = 2, d = 0, a = b^d\), case 2 of Master Method gives \(O(n^d \log n) = O(\log n) = \Theta(\log b)\) (input size is \(b\) here). Option 1 is correct.

Choose the smallest correct upper bound on the solution to the following recurrence: \(T(1) = 1\) and \(T(n) < T(\lfloor \sqrt{n} \rfloor) + 1\) for \(n > 1\). (Note that the Master Method does not apply.)

• \(O(\log n)\)
• \(O(\log{\log n})\)
• \(O(1)\)
• \(O(\sqrt{n})\)

ANSWER: Substitute \(m = \log n\) or \(n = 2^m\), and \(S(m) = T(2^m)\)

\(T(2^m) < T(2^\frac{m}{2}) + 1\)
\(\therefore S(m) < S(\frac{m}{2}) + 1\) (If this is unclear, let \(k = \frac{m}{2}\) and notice all we are doing is \(S(k) = T(2^k)\))
\(\leq S(\frac{m}{2}) + 1\)
\(a = 1, b = 2, d = 0, a = b^d\), Master Method case 1, \(O(\log m) = O(\log{\log n})\). Option 2 is correct.