MA214 Algorithms and Data Structures
2023/24
Exercises 3
(Fibonacci numbers, big-O notation)
Exercise 3.1. Fibonacci numbers, recursively 4 pts
The Fibonacci numbers are a recursively-defined sequence of numbers, which arise in a surprising variety of real-world phenomena. The nth Fibonacci number is usually denoted by Fn and has the following recursive definition:
F1 = 1,
F2 = 1,
Fn = Fn−1 + Fn−2, for n > 2.
(a) Write Python code that, given n ≥ 1 as an argument, implements the natural recursive algorithm for computing the nth Fibonacci number Fn .
(b) Measure the time it takes for computing the nth Fibonacci number Fn for small values of n (up to say 40 or 45): for example, using the code snippet stopwatch.py provided on the course’s Moodle page. Use this to explore the ratio between the running times for two consecutive values of n. What do you observe?
(c) Let a, b > 0 be positive constants. Then, the running time of the recursive algo- rithm is well captured by the following recurrence:
T(n) = T(n − 1) + T(n − 2) + b, for n ≥ 3, and
T(n) = a for n = 1, 2.
Use induction to show that
T(n) = (a + b)Fn − b, for all n ≥ 1.
(d) Assume a = b = 1. The number φ = (1 + √5)/2 ≈ 1.618 is known as the Golden Ratio. Use Binet’s formula for the nth Fibonacci number Fn, given as
to argue that T(n) = Ω(φn ).
Exercise 3.2. Fibonacci numbers, iteratively 3 pts
The natural recursive algorithm for computing the nth Fibonacci number Fn has expo- nential running time. From a time complexity perspective, that is really terrible. From a practical perspective, this means that you will not be able to compute the nth Fibonacci number Fn even for moderately sized values of n using the recursive algorithm.
Luckily, there is a more clever iterative algorithm for computing the nth Fibonacci number that runs in linear time.
(a) Describe this algorithms in words.
(b) Implement this algorithm in Python.
(c) Argue, using big-O notation, that the running time of your algorithm is O(n).
Exercise 3.3. Big O-notation and the sum rule 3 pts
(a) Show that, iff1 (n) = O(g1(n)) and f2 (n) = O(g2(n)), then
f (n) = f1 (n) + f2 (n) = O(g1(n) + g2(n)).
(b) For functions as in part (a), do we also have f (n) = O(max{g1(n), g2(n)})?
(c) Is it also true that iff1 (n) = Ω(g1(n)) and f2 (n) = Ω(g2(n)), then
f (n) = f1 (n) + f2 (n) = Ω(g1(n) + g2(n))?