Share your repls and programming experiences

← Back to all posts
Fast Fibonacci Using Dynamic Programming

This program demonstrates the speed of dynamic programming. For more info on dynamic programming, check out MrEconomical's great tutorial.
Anyways, let's cut to the chase. The attached repl is somewhat of an experiment.

Experiment Setup

The repl is a simple C++ program with 2 functions: fib, which calculates a number in the Fibonacci series using recursion, and dynamic_fib, which calculates a number in the series using dynamic programming.

The Variables

Independent variable:

  • Method (recursive or dynamic)

Dependent variable:

  • Amount of time to calculate the number (in seconds)

The Hypothesis

Calculating a number in the Fibonacci series using dynamic programming will be significantly faster than using recursion.

The Method

The 40th item in the series is calculated by both functions, one after another. Each function is timed, and the function's time is displayed after it finishes. After both functions are done, the difference in time is shown.

The Result

On average, the dynamic method took about 4.5e-05 (0.000045) seconds, and the recursive method took about 1.23 seconds, confirming the hypothesis.

Thanks for reading!


dynamic squids