Algorhithm and Analysis assignment 2

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



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


4.Consider the polynomial p(x) = a0 + a1x + a2x2 +a3x3, 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


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

 C. 7


Categories: NPTEL solution


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

Leave a Reply

Your email address will not be published. Required fields are marked *