Consider a problem that can be solved using a recursive algorithm such as the following:

procedure T ( n : size of problem ) defined as:

if n < 1 then exit

do work of amount f(n)

T(n/b)

T(n/b)

…….. repeat for a total of a times……..

T(n/b)

end procedure

 Algorithms such as above can be represented as a recurrence relation:

T(n) = aT(n/b) + f(n) where a >= 1, b > 1

n is the size of the problem

a is the number of sub problems in the recursion

n/b is the size of each sub problem

f(n) is the cost of the work done outside the recursive calls.

if f(n) = Ɵ(n^c) where c < log_b a (using Big O notation)

then:

T(n) = Ɵ(n^log_b ^a)

If T(n) = 16T(n/2) + 10n²

Then T(n) = Ɵ(???)