Question

Solve this Equation T(n) = 8T(n/2) + n^2 where (T(1) = 1)

Answer 1

apply master theorem T(n) = aT(n/b) +f(n)

a==8

b==2

f(n)=n²  

n^log_ba==>n^log₂^8====>n^log₂2³===>n³  

theorem says

1)if f(n) is polynomial time greater than n^log_ba then answer is ⊝ f(n)

2)if f(n) is polynomial time less n^log_ba then answer is n^log_ba

which is greater then n²   so...answer is ⊝ (n)³