Big Oh Runtime рекурсивной суммы

Question

Если я использую цикл for, чтобы найти сумму n чисел между 0 and n, мое время выполнения равно O(n).Но если я создам рекурсивную функцию, такую ​​как:

int sum(int n) {
    if(n == 0)
        return 0;
    return n + sum((n - 1));
}

Будет ли время выполнения по-прежнему равно O(n)?

Answer 1

@ Ответ Primusa касается вашего рекурсивного вопроса во время выполнения.Хотя мой ответ не касается вашего вопроса во время выполнения, следует отметить, что вам не нужен алгоритм для этого.Закрытая формула для суммы (n+1)*(n) / 2.

, спасибо Карлу Гауссу!

Answer 2

Да, ваше время выполнения все равно будет O(N).Ваша рекурсивная функция будет «зацикливаться» N раза, пока не достигнет базового варианта.

Однако имейте в виду, что сложность пространства также равна O(N).Ваш язык должен сохранить n + ... перед оценкой sum((n - 1)), создавая стек рекурсивных вызовов длиной N.