GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
247 views
asked in Algorithms by (111 points)   | 247 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 (225 points)   | 72 views
+1 vote
1 answer
3
Members at the site
Top Users Feb 2017
  1. Arjun

    4672 Points

  2. Bikram

    4004 Points

  3. Habibkhan

    3738 Points

  4. Aboveallplayer

    2966 Points

  5. sriv_shubham

    2278 Points

  6. Smriti012

    2212 Points

  7. Arnabi

    1814 Points

  8. Debashish Deka

    1788 Points

  9. sh!va

    1444 Points

  10. mcjoshi

    1444 Points

Monthly Topper: Rs. 500 gift card

20,788 questions
25,938 answers
59,531 comments
21,923 users