Сложность времени относительно O (LogN)

Question

Допустим, у нас есть следующий код.

def problem(n):
  list = []
  for i in range(n):
    list.append(i)
    length = len(list) 
  return list

Программа имеет временную сложность O(n), если мы не вычисляем len(list). Но если мы это сделаем, сложность времени будет O(n * log(n)) или O(n^2)? .

Answer 1

Нет, функция len () имеет постоянное время в python и не зависит от длины элемента, ваша временная сложность для приведенного выше кода останется O (N), управляемой вашим циклом for i in range(n). Вот сложность времени для многих функций CPython, таких как len ()! (Получить длину в таблице)