Given algorithm, find and solve the recurrence relation

Question

Consider the following recurrence relation:

$T(2) = 5$

$T(n) = 2T\left( {\left\lceil {{{2n} \over 3}} \right\rceil } \right) + T\left( {\left\lfloor {{n \over 3}} \right\rfloor } \right) + 3$

I got this recurrence relation by analysing the following algorithm:

I got $T(2) = 5$ as the base case because of 2 comparisons in the if statement plus 3 statements in swap() function.

The question requests to solve it using the characteristic equation. However, I don't know how to proceed with the constant $1$ at the end.

My attempt:

$a_n - a_{2n/3} - a_{n/3} = 3 \\ x^n - x^{2n/3} - x^{n/3} = 3 \\ x^{n/3}(x^3 - 2x^2 - 1) = 3$

Also, if I analysed incorrectly the algorithm, please tell me! All help is appreciated!

edit: I incorrectly deduced the recurrence equation. I didn't count the cost of first and second if statement.

Answer 1

Then you can solve your recurrence by putting $$ n = 3m + k = 3\left\lfloor {{n \over 3}} \right\rfloor + n\bmod 3 $$ and split the recurrence into a system three, one for each k.

Answer 2

Too long for a comment.

A good way to simulate it in MATHEMATICA

t[n_] := 2 t[Ceiling[2 n/3]] + t[Floor[n/3]] + 1

t[0] = 0;
t[1] = 0;
t[2] = 5;

tk = Table[{k, t[k]}, {k, 3, 200}]

gr1 = ListPlot[tk]
nlm = NonlinearModelFit[tk, a x^b, {a, b}, x]
gr2 = Plot[Normal[nlm], {x, 0, 400}, PlotStyle -> {Red,Dashed}]
Show[gr1, gr2]