Use the substitution method to prove the running time of the

Use the substitution method to prove the running time of the following recurrence is O(n^3)

Use the substitution method to prove the running time of the following recurrence is O(n^3). T(n) = 2T(n/2) + n^3

Solution

solution

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

we will compare it with T(n)=aT(n/b)+f(n)

so we get, a=2, b=2, f(n)= n^3

As per Master Theorem we have,

T(n)= O(n^3)