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