Geek Answers Handbook

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

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 calculation, solution () loops through AN times and then completes the result M times, thus N + M. However, the online test said that it was instead of N * M, leaving me at a standstill.

+4
source share
2 answers

This is O(M + N); there are no nested loops. This can be reduced to the cost of more; asymptotically, a smaller loop does not matter, making it O(N).

First you iterate over the elements A( Niterations), then separately you iterate over the elements M.

+6
source

O(N), N + M N, M. (, N) , . O(N*M), .

+5

More articles:


All Articles