hard Algorithms

Memoised Fibonacci

The Brief

QuantumLabs is tutoring new devs on algorithmic complexity. They want a demo that shows the same problem solved naively and with memoisation, printing the runtime of each so the difference becomes visceral rather than abstract.

Acceptance Criteria

Tap a criterion to mark it off as you work. Tap a category header to expand or collapse.

1 Implement fib_naive(n) — the simple recursive version

2 Implement fib_memo(n) using either functools.lru_cache or a manual dict cache

3 Time both calls to fib(30) using time.perf_counter

4 Print both results and both elapsed times to 4 decimal places (seconds)

💡 Hints 0 / 3

Guest Mode Attempt this challenge freely, or log in to earn EXP & CodeCoins.

solution.py

Python 3

import time
from functools import lru_cache

def fib_naive(n):
    pass  # TODO

# TODO: fib_memo with caching

# TODO: time both for n = 30 and print results

Console