Проблемы с пониманием времени выполнения комплекса функций

Question

Я сейчас учусь на экзамене, и вопрос в следующем; Данная функция:

def foo(lst):
   count = 0
   while len(lst)>1:
       mid = len(lst)//2
       lst = lst[:mid]
       count += lst[-1]
   return count

Каковы его динамические комплексы?

Насколько я понимаю, внешний цикл while будет запускаться logn раз из-за того, что каждый раз список сокращается пополам. Нарезка - это O (n) -активность, следовательно, время выполнения будет nlogn. К сожалению, ответы утверждают, что время выполнения равно O (n). Где я ошибся?

Answer 1

Краткий ответ : Разделение списка выполняется в O (n) , но, поскольку список каждый раз сокращается пополам, это означает, что n во второй итерации - половина предыдущей.

Если нарезка до k занимает ровно k «инструкции», то это означает, что алгоритм сводится ксумма n / 2 + n / 4 + n / 8 + ... + 1 или более формальная:

log n
---     n
\      ---
/        i
---     2
i=1

Выше приведено геометрическое serie [wiki] равно:

  n/2         n/2
------- - 1 = --- - 1 = n - 1
1 - 1/2       1/2

Таким образом, общее количество инструкций составляет O (n) .