В книге CLRS есть упражнение (17.1-3), которое выглядит следующим образом:
Предположим, мы выполняем последовательность из n операций над структурой данных, в которой затраты на i-ю операцию я, если я точная степень 2, и 1 в противном случае. Используйте совокупный анализ для определения амортизированной стоимости за операцию.
Это перезапись суммирования в предлагаемом ответе, в котором я не уверен. Предлагается следующий ответ:
Итак, мой вопрос - почему / как они переписывают сумму на две части на первом этапе. Почему это правильно с верхней границей log (n) для суммирования?