Большое тета-время выполнения этой рекурсивной функции

Question

Мне нужна небольшая помощь в определении времени работы Big-Theta для этой функции.

int recursive(int n) {

    sum = 0;
    for (int i = 1; i <= n; i++)
        sum++
    if (n > 1)
        return sum + recursive(n-1);
    else
        return n;
}

Я знаю, каково было бы время выполнения этой функции, если бы цикл for не был в функции, но цикл немного сбивает меня с толку. Любой совет?

Answer 1

• Если бы это было только for цикл, не рекурсивный, функция будет O(n),
• Если бы это было просто рекурсивно, и не было for петля, это также будет O(n),
• Но это делает n рекурсивные шаги (которые мы знаем, O(n)) и у него есть O(n)for петля на каждом из n шаги.

Так... это помогает?