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.