Problem

A loop invokes a function called lucas_sequence. lucas_sequence uses recursion to store a sequence of numbers (similar to the Fibonacci sequence) inside memo. What is the time complexity of this algorithm?

for i in range(N + 1):
    print(lucas_sequence(i))
	
memo = {}

def lucas_sequence(n):
    # Base cases
    if n == 0:
        return 2
    if n == 1:
        return 1
    # Check if the result is already in the memo
    if n in memo:
        return memo[n]
    # Otherwise, compute the result and store it in the memo
    result = lucas_sequence(n-1) + lucas_sequence(n-2)
    memo[n] = result
    return result

Solution

We can start with the obvious. The number of loops is linear w.r.t to the input $O(N)$.

for i in range(N + 1):
   lucas_sequence(i)

## ...

Each loop invokes lucas_sequence, so the total time complexity will be $O(N)$ multiplied by the time complexity of lucas_sequence. The runtime of this function is not intuitive, so let's walk through it using our 3-step process.

Pass a few inputs

Assuming that N equals 10.

Loop One

lucas_sequence receives an input of 0 and returns 2.

Loop Two

lucas_sequence receives an input of 1 and returns 1.

Loop Three

lucas_sequence receives an input of 2.

• lucas_sequence(n-1) returns 1.
• lucas_sequence(n-2) returns 2.
• {2, 3} is store inside memo

Loop Four

lucas_sequence receives an input of 3.

• lucas_sequence(n-1) returns the value 3 that matches a key of 2 inside memo.
• lucas_sequence(n-2) returns 1.
• a result of {3, 4} is store inside memo

Loop Five

lucas_sequence receives an input of 4.

• lucas_sequence(n-1) returns the value 4 that matches a key of 3 inside memo.
• lucas_sequence(n-2) returns the value 3 that matches a key of 2 inside memo.
• a result of {4, 7} is stored inside memo

Loop Six

lucas_sequence receives an input of 5.

• lucas_sequence(n-1) returns the value 7 that matches a key of 4 inside memo.
• lucas_sequence(n-2) returns the value 4 that matches a key of 3 inside memo.
• a result of {5, 11} is stored inside memo

Loop Seven

lucas_sequence receives an input of 6.

• lucas_sequence(n-1) returns the value 11 that matches a key of 5 inside memo.
• lucas_sequence(n-2) returns the value 7 that matches a key of 4 inside memo.
• a result of {6, 18} is stored inside memo

Now we can see that there is a clear pattern.

2. How does the runtime increase with the input size.

The number of loops increases linearly with the input size. But regardless of the number that lucas_sequence receives, the number of instructions is constant.

3. Identify the time complexity

The time complexity of the loop is $O(N)$. The time complexity of lucas_sequence is $O(1)$. The total time complexity is $O (N * 1)$ $=>$ $O(N)$.

Common Mistake

A common mistake would have been to automatically assume that lucas_sequence has a time complexity of $O(2^N)$ because of its recursive calls, when in fact it's $O(1)$.

Sometimes the time complexity is very obvious (as was the case with the previous 7 problems). But this problem presents a scenario where you must walk through the runtime and fully understand how the algorithm works before approximating the time complexity.

---

This workbook was created by Jad and Rayan Slim. Feel free to explore some of their courses:

The Complete Java Development Bootcamp

The Complete Spring Boot Development Bootcamp – Become a Java Web Developer