GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
628 views
asked in Algorithms by (111 points)   | 628 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 (9.4k 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 (539 points)  

Related questions

+1 vote
2 answers
1
0 votes
1 answer
2
asked in Algorithms by iarnav Active (2.3k points)   | 88 views
+1 vote
1 answer
3


Top Users Aug 2017
  1. ABKUNDAN

    4670 Points

  2. Bikram

    4556 Points

  3. akash.dinkar12

    3420 Points

  4. rahul sharma 5

    3124 Points

  5. manu00x

    2864 Points

  6. makhdoom ghaya

    2450 Points

  7. just_bhavana

    2136 Points

  8. Tesla!

    2042 Points

  9. stblue

    1930 Points

  10. joshi_nitish

    1686 Points


24,970 questions
32,072 answers
74,567 comments
30,150 users