이 재귀 함수의 큰 세타 실행 시간

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; 
} 

나는 루프의 함수에없는 경우이 함수의 실행 시간이 될 것입니다 무슨 방법을 알고 있지만, 루프는 조금 날을 던지고있다. 어떤 충고?

Answer 1

• 루프가 for 인 경우 재귀가 아닌 경우 O(n)이됩니다.
• 재귀적인 경우에만 for 루프가 없으면 O(n)이됩니다.
• 그러나, 그것은이 n 각 단계에서 O(n)for 루프를 가지고 및 (우리가 O(n) 알고) n 재귀 단계를하고있어.

그래서 ... 도움이 되나요?