Question

Solve this equation T(n) = 7T(n/2) + n^2

Comments

plz give me ans by back substitution.....

Answer 1

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)

Comments

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)

---

so what will be the answer, according to the extended master theorem,

T(n) = Θ (n^2.80735) that is approximate value of  θ(n³) 

Answer 2

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

T(n)=n^log₂7 =n^{2.81 i.e f(n) is polynomially smaller than t(n), therefore it is first case}

 ^{therefore, ans is} ⊖(n^log7) or ⊖(n^2.81)