Assume in a divide and conquer algorithm we always divide an

Assume, in a divide and conquer algorithm, we always divide an instances of size n of a problem into 10 sub instances of size n/3, and the dividing and combining steps take a time in O(n^2). write a recurrence equation for the running time t(n), and solve the equation for t(n).

Solution

Answer:

The recurrence equation for the running time t(n) is :

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

Always follow T(n) = aT(n/b) + f(n)
a = no of sub problems
f(n) = time to divide and combine the subproblems.

Now , we can solve the equation using Masters theorm

Here a = 10 , b = 3 , c = 2

log10 base 3 = 1 ( approx)

but c > loga base b , therefore T(n) = theta( n^c) => T(n) = theta(n^2)