Как рассчитывается сложность времени O (n)?

Question

Предположим, что следующий код (Python) - Лидер в массиве

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

Так, так как мы пересекаем массив A дважды, временная сложность должна быть O (n + n)

Но упоминается, что временная сложность будет O (n)

Почему?

Answer 1

Обозначение O касается только порядка n (другими словами, степень n). Таким образом, все, в чем n возводится в степень 1, считается O(n), например, O(n), O(2n), O(n+1) et c.

Аналогично, O(n^2), O(n^2+2n) et c все считаются O(n^2).