Consider the generic algorithm SolveP given below, which solves a

problem $P$ by finding the output $($solution$)O$ that corresponds to an input I.

ALGORITHM SolveP$($input I, output& O$)$

$//$ Input: I $($of size $n)$ for problem $P$

$//$ Output: O$,$ the solution to problem P

if size $($I$)==1$

compute solution $0$ to basic problem directly

else

partition I into $5$ inputs $I_1,I_2,$dots,$I_5,$ of size $\frac{n}{3}$ each

for jlarr$1$ to $5$ do

SolveP $(\{$:$I_j,O_j)$

Combine $O_1,O_2,$dots,$O_5$ to get solution $O$ for $P$ with input $I$

Assume that the algorithm performs $g(n)$ operations for partitioning and combining and no

basic operations for an instance of size $1.$ Write and solve the recurrence equation $T(n)$ for

the number of basic operations needed to solve $P$ when the input size is $n$ and $g(n)=nlgn.$