Twelve Simple Algorithms to Compute Fibonacci Numbers

Abstract

The Fibonacci numbers are a sequence of integers in which every number after the first two, 0 and 1, is the sum of the two preceding numbers. These numbers are well known, and the algorithms to compute them are simple enough that they are often used in introductory algorithms courses. In this paper, we present twelve such algorithm together with their time and space complexity analyses. Though very simple, these algorithms illustrate eleven concepts from the algorithms field, ranging from top-down vs. bottom-up dynamic programming to recursion depth, and we say which algorithms illustrate which concept. We also present the results of a small-scale experimental comparison of their runtimes on a personal laptop, where the slowest algorithm takes about four orders of magnitude longer than the fastest. Finally, we provide a list of homework questions for students. We hope that this paper can serve as a useful resource for students learning the basics of algorithms.