Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

migrated from scicomp.stackexchange.com Jun 15 '13 at 2:28

This question came from our site for scientists using computers to solve scientific problems.

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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