In this article i am gone to share Coursera Course Divide and Conquer, Sorting and Searching, and Randomized Algorithms Week 2 | Problem Set #2 Quiz Answer with you..

Divide and Conquer, Sorting and Searching, and Randomized Algorithms

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 )