Given the following code:
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) 
 }
I would like to find g(n) so that T(n)=THETA(g(n)).
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.