Divide and Conquer, Sorting and Searching, and Randomized Algorithms Week 2 | Problem Set #2 Quiz Answer
Problem Set #2
Question 1)
This question will give you further practice with the Master Method. Suppose the running time of an algorithm is governed by the recurrence T(n) = 7 ✳ T(n / 3) +n2. What's the overall asymptotic running time (i.e, the value of T(n))?
- Ó¨(n2 log n)
- Ó¨(n2)
- Ó¨(n2.81)
- Ó¨(n log n)
Question 2)
This question will give you further practice with the Master Method. Suppose the running time of an algorithm is governed by the recurrence T(n) = 9✳T(n / 3) +n2. What's the overall asymptotic running time (i.e, the value of T(n))?
- Ó¨(n2 log n)
- Ó¨(n2)
- Ó¨(n3.17)
- Ó¨(n log n)
Question 3)
This question will give you further practice with the Master Method. Suppose the running time of an algorithm is governed by the recurrence T(n) = 5✳T(n / 3) +4n. What's the overall asymptotic running time (i.e, the value of T(n))?
- Ó¨(n2.59)
- Ó¨(n2)
- Ó¨(nlog 3 / log 5)
- Ó¨(n5/3)
- Ó¨(n log (n))
- Ó¨(nlog 3 / (5))
Question 4)
Consider the following pseudocode for calculating a where a and bare positive integers)
FastPower(a,b) :
if b = 1
return a
else
c : = a*a
ans := Fast Power(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 (Le.. 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)?
- Ó¨(b log(b))
- Ó¨(log(b))
- Ó¨(b)
- Ó¨(√b)
Question 5)
Choose the smallest correct upper bound on the solution to the following recurrence T(1) = 1 and T (n) ≤ T( [√n]) +1 for n > 1. Here [x] denotes the "floor” function, which rounds down to the nearest integer. (Note that the Master Method does not apply.)
- 0(log n)
- 0(√n)
- 0(1)
- 0(log log n )
