Why is list5 complexity5?

Q&A DQ Courses
, ,
#1

Screen Link:

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?

#2

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

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?

thanks in advance

1 Like
#4

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

1 Like
#5

Hello @eby.annie, @scarlett.patrick22,

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 Order 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 Order(N*M)


Hope this clears it up!
Do let me know.

3 Likes
#6

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

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?