Big O
)}

# 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.

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

Feedback Summary
0.0
0 students
5

0%
4

0%
3

0%
2

0%
1

0%
Written Reviews
There are no written reviews yet.