GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
313 views
asked in Algorithms by (111 points)   | 313 views
plz give me ans by back substitution.....

Here is an explaination for the solution http://techieme.in/solving-recurrences-master-method/

2 Answers

+1 vote

T(n) = 7T(n/2) + n^2

comparing with the equation (MASTER THEOREM)

T(n) = aT(n/b) + ⊖(n^k $\log_{n}p$)

we get ,a=7,b=2,k=2,p=0

now it satisfies a>b^k,

so case first of master theorem

T(n) = ⊖(n^$\log_{b}a$)

T(n)=⊖(n^3)

answered by Boss (8.1k points)  
T(n) = n^2.801
we know by master theoram

T(n) = aT(n/b) + n^klogp(base n)

where a>=1 , b>1 , k>=0 and p is a real number

In above question a =7, b=2 , k=2 and p=0

if a>b^k

then Tc = O(n^loga(base b))

            = O(n^log7(base 2))

            =O(n^3)
0 votes

Compare with master theorem ,a=7,b=2 and f(n)=n2

T(n)=nlog27 =n2.81 i.e f(n) is polynomially smaller than t(n), therefore it is first case

 therefore, ans is (nlog7) or (n2.81)

answered by Junior (523 points)  

Related questions

+1 vote
2 answers
1
0 votes
1 answer
2
asked in Algorithms by yourarnav (237 points)   | 73 views
+1 vote
1 answer
3


Top Users Mar 2017
  1. rude

    4018 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2608 Points

  5. Debashish Deka

    2104 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1336 Points

  8. Bikram

    1218 Points

  9. Akriti sood

    1186 Points

  10. Sanjay Sharma

    1016 Points

Monthly Topper: Rs. 500 gift card

21,446 questions
26,757 answers
60,937 comments
22,954 users