1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ There is more material on this method here. $\endgroup$ – Marko Riedel Jun 14 '13 at 21:27
1
$\begingroup$

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
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The G is the one I am searching for, thanks. $\endgroup$ – M.K. aka Grisu Jun 14 '13 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.