Problem Set 2

Suppose the running time of an algorithm is governed by the recurrence . What’s the overall asymptotic running time (i.e., the value of )?

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

ANSWER: Applying the Master Method, , case 2, work done at the root dominates the running time, therefore, running time is . Option 2 is correct.

Suppose the running time of an algorithm is governed by the recurrence . What’s the overall asymptotic running time (i.e., the value of )?

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

ANSWER: Applying the Master Method, , work done at every level is the same, case 1, therefore, running time is . Option 2 is correct.

Suppose the running time of an algorithm is governed by the recurrence . What’s the overall asymptotic running time (i.e., the value of )?

  • \(\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, , work done = number of leaves, case 3, therefore, running time is . Option 2 is correct.

Consider the following pseudocode for calculating (where and 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 denotes the floor function, that is, the largest integer less than or equal to .

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 )?

  • \(\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, , case 2 of Master Method gives (input size is here). Option 1 is correct.

Choose the smallest correct upper bound on the solution to the following recurrence: and for . (Note that the Master Method does not apply.)

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

ANSWER: Substitute or , and


(If this is unclear, let and notice all we are doing is )

, Master Method case 1, . Option 2 is correct.