CODEWITHSUNDEEP
c++algorithmtime-complexityruntimecomplexity-theory
Francisco d'Anconia
Francisco d'Anconia

Reputation: 11

Complexity of a recursive function c++

*I'm trying to calculate the complexity Big-Theta-Notation of the following function: variable i is constant == 3 * 

void g(int i, int n) {
    if (i>0) {
        for (int j=n+10; j>0; j-=5) {
            g(i-2, n);
        }
    }
}

Because it's a recursive function, I thought I should calculate it with Master Theorem, but actually there is no division of n. I would be very greatful for any kind of help!

Upvotes: 0

Views: 90

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58221

The recurrence relation is T(i, n) = (n+10)T(i-2, n)/5.

The terms for both odd and even i are geometric progressions with the multiplication factor (n+10)/5. This solves to T(i, n) = O((n/5)^(i/2)), or O(sqrt(n/5)^i) if you prefer.

Upvotes: 0

Related Questions