Given the following code:
I would like to find g(n) so that T(n)=THETA(g(n)).
if (r ≤ p+n^1/3)
t := |_(r-p+1) /3_|
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.