2

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?

M.K. aka Grisu
  • 135

1 Answers1

6

You have too much recursion because your code assumes nto be even for the stopping criterion to work. If you call your flops count function with nequal to 3, it will call the function with argument 3/2and your recursion will never end. You could replace your function with

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

and use the criterion flops(0) := 0

But this will only work if you use numbers, not some arbitrary N. If you want to solve the recurrence equation, you should use the rsolvecommand:

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

which will give you $\frac{1072}{9}n(n^2-1)$ as an answer to your problem.

GertVdE
  • 176