Why is list2 complexity1 ? Shouldn't it be complexity 2?

Screen Link:

https://app.dataquest.io/m/477/constant-time-complexity/4/hidden-function-calls

My Code:

N = 10
M = 20

list1 = [_ for i in range(0)]
list2 = [i for i in range(3)]
list3 = [i * i for i in range(M)]
list4 = [[i + j for j in range(M)] for i in range(N)]
list5 = [min(list4[i]) for i in range(N)]
list6 = [i for i in range(1000)]

complexity1 = 'O(1)'
complexity2 = 'O(N)'
complexity3 = 'O(M)'
complexity4 = 'O(N + M)'
complexity5 = 'O(N * M)'

# Example answer for list1
answer1 = complexity1
answer2 = complexity1
answer3 = complexity3
answer4 = complexity5
answer5 = complexity5
answer6 = complexity2

What I expected to happen:

What actually happened:

Replace this line with the output/error
2 Likes

This can be a bit confusing to grasp at first.

Time complexity, broadly speaking, talks about how the execution time of a particular code/function/algorithm grows depending on the size of the data (N).

And this is the important distinction point -

If the order is O(N) that means that the execution time grows linearly as N increases.

But, what if N is the same value? What if it’s the same value every time the code is executed?

Then the execution time for that code will always be the same. Because if the input to that code, N is not changing, then the execution time for that code [mostly] won’t change either.

This is what they explain in Step 2 of this Mission as well.

The function sum_1000() does one thing. Computes the sum of the first 1000 integers.

Every time you call sum_1000() it will do that exact same thing. So, it’s execution time is not changing with the number of integers here. Because the number of integers is always 1000.

If you modified the function to something like -

def sum_N():
    total = 0
    for i in range(N):
        total += i
    return total

The time complexity of the above would be O(N), because N could be any value. And with higher/larger N, the time complexity would be higher.

It’s the same for -

list2 = [i for i in range(3)]

Since that 3 is not changing. Any time that particular piece of code is run, you will get [almost] the same execution time. If instead of that 3 we had an N, then we could say that the time complexity is O(N) because N would be a variable whose value could be different.

3 Likes