Is this function O(N+M) or O(N*M)?

Question

def solution(M, A):
    result = [0] * M
    maxCount = 0
    setAll = 0

    for i in range(0,len(A)):
        if (A[i] == M + 1):
            setAll += maxCount
            maxCount = 0
            result = [0] * M
        else:
            result[A[i] - 1] += 1

            if (result[A[i] - 1] > maxCount):
                maxCount = result[A[i] - 1]

    for j in range(0,len(result)):
        result[j] += setAll

    return result


A = [ 1, 1, 1, 1, 2, 3] 
M = 2

print solution(M, A) # result = [ 4, 4 ]


A = [ 1, 2, 2, 4, 1, 1] 
M = 3

print solution(M, A) # result = [ 4, 2, 2 ]

By my count, solution() loops through A N times and then loops result M times thus N+M. However, an online test said that it was instead N*M, leaving me stumped.

Martijn Pieters · Accepted Answer · 2013-11-09T17:27:36.360

6

It is O(M + N); there are no nested loops here. This can be reduced to the cost for the larger number; asymptotically, the smaller loop is not going to matter, making it O(N).

First you loop over A elements (N iterations), then separately you loop over M elements.

edited Nov 09 '13 at 17:27

answered Nov 09 '13 at 17:21

Martijn Pieters

1,048,767
296
4,058
3,343

1

I don't see nested loops... am I missing something? – Brad Allred Nov 09 '13 at 17:27
Yes, the word 'no' was missing. :-P Oops! – Martijn Pieters Nov 09 '13 at 17:27
I *do* see a nested loop (kind of): `for i in range(0,len(A)): ... result = [0] * M`. Creating the right hand side of the assignment should be Theta(M), doing this N times is Theta(O*N) (worst case). – Reinstate Monica Nov 24 '13 at 23:19

joews · Answer 2 · 2013-11-09T17:29:10.410

5

It is O(N), because the there are N + M loops for a given input N, M. That reduces to the larger of the two (let's say that is N) for the purposes of time complexity, because we only take the most significant term. It would be O(N*M) if the second loop was nested inside the first.

edited Nov 09 '13 at 17:29

answered Nov 09 '13 at 17:23

joews

29,767
10
79
91

Is this function O(N+M) or O(N*M)?

2 Answers2

Linked