Comparing time complexity for making list to set in a for loop and x in list in a for loop

user_5846131 0
Viewed 68

I'm doing the GenomicRangeQuery exercise from Codility. (I don't paste the question here, because it is a bit too long.)

This is my answer and it has passed the tests. And it shows the Detected time complexity is O(N + M).

def solution(S, P, Q):
    impacts_dic = {"A": 1, "C": 2, "G": 3, "T": 4}

    result = []
    for i in range(len(P)):
        if P[i] == Q[i]:
            result.append(impacts_dic[S[P[i]]])
            continue

        impact_list = S[P[i]:Q[i] + 1]

        if "A" in impact_list:
            result.append(impacts_dic["A"])
        elif "C" in impact_list:
            result.append(impacts_dic["C"])
        elif "G" in impact_list:
            result.append(impacts_dic["G"])
        else:
            result.append(impacts_dic["T"])

    return result

Example test:

S = "CAGCCTA"

P = [2, 5, 0]
Q = [4, 5, 6]
print(solution(S, P, Q))

print(solution('A', [0], [0]))

But I don't quite understand why the time complexity is O(N + M)?

The time complexity for "for loop" is O(M) and "x in s" for list is O(len(impact_list)), where len(impact_list) <= N. But why the time complexity is not O(N * M)?

I also don't understand how to calculate the time complexity for my first try answer. Instead of impact_list = S[P[i]:Q[i] + 1] I wrote impact_set = set(S[P[i]:Q[i] + 1]), and the time complexity is O(N * M). I think it is because the time complexity for make the list to set is O(n), and n <= N.

Comparing these two, why the first one is plus M and N but the second one is multiply M and N?

time-complexity python
1 Answers

The detected time is wrong, and your manual analysis is right. Both solutions are O(N * M).

The shape of the curve doesn’t become visible for a while, so some automated methods might make a mistake, especially when Python operations can have vastly different constant factors.

I plotted the output of this program that sets N = M:

import timeit


def solution(S, P, Q):
    impacts_dic = {"A": 1, "C": 2, "G": 3, "T": 4}

    result = []
    for i in range(len(P)):
        if P[i] == Q[i]:
            result.append(impacts_dic[S[P[i]]])
            continue

        impact_list = S[P[i]:Q[i] + 1]

        if "A" in impact_list:
            result.append(impacts_dic["A"])
        elif "C" in impact_list:
            result.append(impacts_dic["C"])
        elif "G" in impact_list:
            result.append(impacts_dic["G"])
        else:
            result.append(impacts_dic["T"])

    return result


def measure(n, m):
    return timeit.timeit(lambda: solution("C" * n, [0] * m, [n - 1] * m), number=3)


for n in range(1, 100002, 1000):
    print(f"{n}\t{measure(n, n):f}")

and as you can see, it’s a parabola, not the straight line you’d expect for O(N + M):

plot of time against input size

user_7071110
Related