Временная сложность повторения пустого списка

Question

В следующем коде, какова будет наилучшая сложность случая? В лучшем случае ввод пустой список, что означает, что цикл не повторяется и, следовательно, O (1)? Или вы должны рассматривать его как цикл, который всегда повторяется n раз и, следовательно, O (n), независимо от ввода?

def f(L, x): 
    n = len(L) 
    c = 0 
    for i in range(n): 
        if L[i] == x: 
            c = c + 1 
    return c 

Answer 1

Это всегда будет O (n), так как независимо от ввода цикл всегда будет повторяться n раз. N, равное 1, не сделает сложность когда-либо равной O (1), O (1) зарезервировано только для атомарных операций, независимо от того, что будет O (1).

В основном O (N) относится к тому факту, что время этого фрагмента кода линейно зависит от N.