Если бы мы захотели максимально полно описать эффективность этого алгоритма, то сказали бы, что сложность линейного поиска равна O(1) в лучшем случае и O(N) — в худшем.