Algorhithm and Analysis assignment 2

**1. If T(n)=9T(n/3)+n, then by master method T(n)= **

B.Θ(n^2)

**2. If T(n)=T(2n/3)+1, then by master method T(n)= **

A. Θ(nlogn)

**3.If T(n)=2T(n/2)+ Θ(n), then by master method T(n)= **

D.Θ(nlogn)

**4.Consider the polynomial p(x) = a _{0} + a_{1}x + a_{2}x^{2} +a_{3}x^{3}, where ai≠ 0, for all i. The minimum number of multiplications needed to evaluate p on an input x is:**

A. 3

**5. Naive matrix multiplication of two N×N matrices has running time **

C. Θ(N^3)

**6.Strassen’s method has running time (for multiplying two n×n matrices) **

D. None of the above

**7.Divide and conquer consists of **

B. Divide,Conquer and Combine

**8.If T(n) = T(n/4) + T(n/2) +n2 , then using recursion tree method **

B. T(n)=Θ(n^2)

**9.Recurrence relation for binary search **

T(n)=T(n/2)+Θ(1)

**10. Strassen’s algorithm needs____ many multiplications to multiply two 2×2 matrices **

C. 7

## 5 Comments

## Rishab · August 13, 2017 at 6:08 PM

can you give a explanation for ques 4

## Rishab · August 13, 2017 at 6:09 PM

Please upload solutions for week 3

## Smit Parmar · August 14, 2017 at 7:53 AM

Thanks for visiting our site,

Now you can check week 3 solution

## Viva Masell · September 2, 2017 at 1:49 AM

This is my first visit here. I found some really interesting stuff in your blog especially this discussion. Keep up the good work.

## Mit Patel · September 5, 2017 at 7:31 PM

Thanks for feedback. Keep visiting.

~Because here we aim to please