# 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.