Count # времени основной работы выполняется

Question

Я дал этот алгоритм для вычисления суммы первых п кубов:

s(n) { 
    if (n == 1) { 
    return 1 
    } else { 
    return s(n - 1) + n * n * n 
    } 
} 

Для подсчета количества раз основная операция выполняется, я спросил использовать следующее рекуррентное соотношение: T(1) = 0 и T(n) = T(n - 1) + 2

Может кто-нибудь объяснить мне, почему отношение выглядит так, а точнее: откуда взялось число 2?

Если n = 2, на мой взгляд, T(2) = 1, поскольку умножение выполняется только один раз, но по формуле T(2) = 2.

Answer 1

Сложность заключается в сложности выполнения операции умножения, которая происходит дважды на каждой итерации из-за n * n * n. Также отметим, что T(2) = 2:

T(2) = T(1) + 2 
    = 0 + 2 
    = 2 

В целом сложность этого алгоритма является O(2n) что эквивалентно O(n), и алгоритм может быть записан в виде простой цикл:

s(n): 
    r := 0 
    for i := 1 to n 
     r := r + i * i * i 
    return r