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.