How do i check the time complexity of a comprehension

Question

I have gone through many blogs regarding python time complexity and posting my doubt:

In case of list comprehensions how will the time complexity be analysed?

For example:

x = [(i,xyz_list.count(i)) for i in xyz_set]

where xyz_list = [1,1,1,1,3,3,4,5,3,2,2,4,5,3] and xyz_set = set([1, 2, 3, 4, 5])

So, is the complexity the one line of code O(n*n*n) [i.e., O(n) for iteration, O(n) for list creation, O(n) for count function]??

Answer 1

This is quadratic O(n^2):

x = [(i,xyz_list.count(i)) for i in xyz_set]

xyz_list.count(i)) #  0(n) operation

for every i in xyz_set you do a 0(n) xyz_list.count(i)

You can write it using a double for loop which will make it more obvious:

res = []
for i in xyz_set: # 0(n)
    count = 0
    for j in xyz_list: # 0(n)
        if i == j: # constant operation 0(1) 
            count += 1 # constant operation 0(1)
    res.append(count) # constant operation 0(1)

Python time complexity

usually when you see a double for loop the complexity will be quadratic unless you are dealing with some constant number, for instance we just want to check the first 7 elements of xyz_list then the running time would be 0(n) presuming we are doing the same constant work inside the inner for:

sec = 7
res = []
for i in xyz_set: 
    count = 0
    for j in xyz_list[:sec]: 
        ......