# Why is list5 complexity5?

Goal: identify the correct complexity:

``````list5 = [min(list4[i]) for i in range(N)]
``````

What I expected to happen:
I thought this would be this time complexity:

``````complexity2 = 'O(N)'
``````

What actually happened:
But it says the answer is

``````complexity5 = 'O(N * M)'
``````

Why is it N*M and not just N?

Hi @eby.annie:

In the list comprehension there are 2 operations: the looping as well as the indexing, so its not just a single dimension of complexity and we tag each arbitrarily to `O(n)` and `O(m)` respectively. Since the two operations occur, we will use their product to compute the complexity of the algorithm. Also since its not a nested loop (of same type/functionality), thus it isnâ€™t `O(n^2)`.

Hope this clarifies!

2 Likes

Hello

I still donâ€™t get it. If, as it says in the next screen of this mission, we can directly access the list (size N*M) element that we are passing as an argument, and then we are comparing this N times to find the minimum, shouldnâ€™t the order be N?

1 Like

In Big O Notation `O()` represents the worst case scenario

1 Like

I will try my best to clarify as I was in the same boat as you.
This is how I see it:

``````# Let's say..
N = 10
M = 20

list4 = [[i + j for j in range(M)] for i in range(N)]  # N*M
list5 = [min(list4[i]) for i in range(N)]
``````

This is what `list4` holds:

``````for i, v in enumerate(list4):
print(f"{i}: {v}")

Output:
0: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
1: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
2: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]
3: [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
4: [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23]
5: [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
6: [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
7: [7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]
8: [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27]
9: [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]
``````

As you see, the length of each entry in `list4` is not the same as `N`.
The maximum length we see is at `list4[9]`. It is of length 20, which is the value of `M`.

Letâ€™s see this for the worst-case scenario because the `O`rder of Time complexity is measured against the worst case:

Even though accessing a list by its index is a constant time operation `O(1)`,
`list5 = [min(list4[i]) for i in range(N)]` translates to:
`list5 = [min(list4[9]) for 9 in range(0..9)]` when `i = 9`, which again translates to:
`list5 = [min([9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28])]`

Now, what is the cost of performing `min(list4[9])` whose size is `M`?
The whole list of size `M` is scanned to find the minimum.
This is the cost of the hidden operation.

So for every `N`, the hidden cost is `M`, which is of the `O`rder`(N*M)`

Hope this clears it up!
Do let me know.

4 Likes

Thankyou Sanjeeve

Yes, this does help, I can see where the M comes from now.

I was imagining List 4 as 200 tuples (0:0), (0:1) etc, rather than ten tuples with the second value being a list (0:[0,1,2,3 etc])

thank you

Scarlett

1 Like

Hi all,
I was under the impression that list5 would have to complexity O(MN^2) as list4 has (MN) and list5 iterates N times over it. So (M*N)N = MN^2, but I guess there is something wrong with this. Can anyone explain to me where I am making a false assumption?

Hi marie.loup.turenne, I had the same question. Did you ever get it resolved? Cheers.