# Simplify a recursively defined function in Maple

I have the following problem. Out of the runtime analysis of an divide and conquer algorithm I got the following formula for the necessary flops:

flops(n): = (89+1/3)*n^3 + 2 * flops(n/2)


and

flops(1):= 0


I want to sum it up and to remove the recursion with Maple. But I do not get it working. Everytime Maple complains: Error, (in flops) too many levels of recursion

How can this be done?

We can actually do a little more and find an exact solution to this recurrence. First solve for $S(n)$ where $S(0)=0$ and $$S(n) = 268/3 n^3 + 2 S(\lfloor n/2\rfloor).$$

Let $$n = \sum_{k=0}^{\lfloor\log_2 n\rfloor} d_k 2^k$$ be the binary representation of $n.$ By inspection we see that $$S(n) = 268/3 \sum_{j=0}^{\lfloor\log_2 n\rfloor} 2^j \left(\sum_{k=j}^{\lfloor\log_2 n\rfloor} d_k 2^{k-j}\right)^3.$$ This formula is exact.

We are interested in $T(n)$ which has the same recurrence as $S(n)$ but with $T(1)=0.$ (We have $S(1)=268/3.$) So this gives $$T(n) = -268/3 \times 2^{\lfloor\log_2 n\rfloor} + 268/3 \sum_{j=0}^{\lfloor\log_2 n\rfloor} 2^j \left(\sum_{k=j}^{\lfloor\log_2 n\rfloor} d_k 2^{k-j}\right)^3.$$ This formula is exact, too.

To do the asymptotics we need upper and lower bounds. An upper bound occurs for a string of one digits, giving $$T(n) \le 268/3 \left(32/3\times 2^{3\lfloor\log_2 n\rfloor} -24\times 2^{2\lfloor\log_2 n\rfloor} + 37/3 \times 2^{\lfloor\log_2 n\rfloor} + 6\lfloor\log_2 n\rfloor 2^{\lfloor\log_2 n\rfloor} +1\right).$$ We get the lower bound by considering a one followed by a string of zeros, giving $$T(n) \ge 268/3 \left(4/3 \times 2^{3\lfloor\log_2 n\rfloor} - 4/3 \times 2^{\lfloor\log_2 n\rfloor}.\right).$$ If we put $m = 2^{\lfloor\log_2 n\rfloor}$ this becomes $$268/3 \left(4/3 \times m^3 - 4/3 \times m\right) = 1072/9 \; m \; (m^2-1),$$ which is the result that acer computed in his post. The asymptotically dominant terms are $$268/3 \times 32/3\times 2^{3\lfloor\log_2 n\rfloor} \quad \text{and} \quad 268/3 \times 4/3 \times 2^{3\lfloor\log_2 n\rfloor},$$ so that $$T(n) \in \Theta\left(2^{3\lfloor\log_2 n\rfloor}\right) = \Theta\left(2^{3\log_2 n}\right) = \Theta(n^3),$$ in accordance with the Master theorem.

• There is more material on this method here. – Marko Riedel Jun 14 '13 at 21:27

Are you intending that n and integer and a power of 2?

restart:

Flops:=proc(N::rational)
if N<=1 then return 0;
else (89+1/3)*N^3+2*procname(N/2);
end if;
end proc:

seq(Flops(2^i), i=0..4);

0, 2144/3, 21440/3, 60032, 1457920/3

G:=unapply(rsolve({flops(n)=(89+1/3)*n^3+2*flops(n/2),flops(1)=0},
flops),
n);

2
G := n -> 1072/9 n (n  - 1)

seq(G(2^i), i=0..4);

0, 2144/3, 21440/3, 60032, 1457920/3

• The G is the one I am searching for, thanks. – M.K. aka Grisu Jun 14 '13 at 14:50