15. Consider algorithm solve given below. This algorithm solves problem P by finding the output (solution) O corresponding to any input I.

void solve (input I, output& O) { if (size (I) == 1) find solution O directly; else{ partition I into 5 inputs I1, I2, I3, I4, I5, where size (Ij) = size (I)/3 for j = 1, ..., 5; for (j = 1; j < = 5; j++) solve (Ij, Oj); combine O1, O2, O3, O4, O5 to get O for P with input I; } }

Assume g (n) basic operations for partitioning and combining and no basic operations for an instance of size 1.

Find the general solution for n a power of 3 for the recurrence of the above pseudocode known as T(n) = 5 x T(n/3) + g(n).

Please be descriptive as much as possible. Especially when a transition between n to k needs to occur and describe why we are transitioning between variables all of the sudden. Thanks.