Given the following code:

I would like to find g(n) so that T(n)=THETA(g(n)).Code:Alg(A,n,p,r) { if (r ≤ p+n^1/3) Proc1(A,p,r) else { t := |_(r-p+1) /3_| Alg(A,n,p,p+t-1) Alg(A,n,p+t,p+2t-1) Alg(A,n,p+2t,r)) Proc2(A,p,r) }

It is given that 1<=p, r<=n for A[r...p]. For p=1 and r=n it is given that the running time of Proc1 is cn^2 and the running time of Proc2 is c'n. T(n) is the running time of Alg. It is stated that I may also assume that n=3^k.

Here's a conjecture:

Would it be correct to say that T(n)=c'n+cn^2+3T(n/3)? If so, I could possibly use the Master Theorem to find g(n).

I'd appreciate some guidance.