CODEWITHSUNDEEP
pythonarrayspython-3.xperformancetime-complexity
manish kumar
manish kumar

Reputation: 4692

How the time complexity O(n) is calculated?

Lets assume the following code (Python)- Leader in the array

def goldenLeader(A):
    n = len(A)
    size=0
    for k in xrange(n):
       if (size == 0): size += 1
          value = A[k] else:
       if (value != A[k]): size -= 1
       else:
         size += 1
    candidate = -1 if (size > 0):
    candidate = value leader = -1
    count = 0
    for k in xrange(n):
        if (A[k] == candidate): count += 1
    if(count>n//2): leader = candidate
    return leader

So Since we are traversing the array A twice ,the time complexity should be O(n + n)

But it is mentioned the time complexity to be O(n)

How come?

Upvotes: 0

Views: 61

Answers (1)

DeepSpace
DeepSpace

Reputation: 81604

The O notation only cares about the order of n (in other words, the power of n). So, anything in which n is raised to the power of 1 is considered O(n), eg O(n), O(2n), O(n+1) etc.

Similarly, O(n^2), O(n^2+2n) etc are all considered to be O(n^2).

Upvotes: 1

Related Questions