Big-O complexity recursion Vs iteration

Question

Question 5 on Determining complexity for recursive functions (Big O notation) is:

int recursiveFun(int n)
{
    for(i=0; i<n; i+=2)
        // Do something.

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun(n-5);
}

To highlight my question, I'll change the recursive parameter from n-5 to n-2:

int recursiveFun(int n)
{
    for(i=0; i<n; i+=2)
        // Do something.

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun(n-2);
}

I understand the loop runs in n/2 since a standard loop runs in n and we're iterating half the number of times.

But isn't the same also happening for the recursive call? For each recursive call, n is decremented by 2. If n is 10, call stack is:

recursiveFun(8)
recursiveFun(6)
recursiveFun(4)
recursiveFun(2)
recursiveFun(0)

...which is 5 calls (i.e. 10/2 or n/2). Yet the answer provided by Michael_19 states it runs in n-5 or, in my example, n-2. Clearly n/2 is not the same as n-2. Where have I gone wrong and why is recursion different from iteration when analyzing for Big-O?

Answer 1

Common way to analyze big-O of a recursive algorithm is to find a recursive formula that "counts" the number of operation done by the algorithm. It is usually denoted as T(n).

In your example: the time complexity of this code can be described with the formula:

T(n) = C*n/2                                   +    T(n-2)
       ^                                              ^
    assuming "do something is constant        Recursive call

Since it's pretty obvious it will be in O(n^2), let's show Omega(n^2) using induction:

Induction Hypothesis:

T(k) >= C/8 *k^2  for 0 <= k < n

And indeed:

T(n) = C*n/2 + T(n-2) >= (i.h.) C*n/2 + C*(n-2)^2 / 8
     = C* n/2 + C/8(n^2 - 4n + 2) =
     = C/8 (4n + n^2 - 4n + 2) =
     = C/8 *(n^2 + 2)

And indeed:

T(n) >= C/8 * (n^2 + 2) > C/8 * n^2

Thus, T(n) is in big-Omega(n^2).

Showing big-O is done similarly:

Hypothesis: T(k) <= C*k^2 for all 2 <= k < n

T(n) = C*n/2 + T(n-2) <= (i.h.) C*n/2 + C*(n^2 - 4n + 4) 
     = C* (2n + n^2 - 4n + 4) = C (n^2 -2n + 4)

For all n >= 2, -2n + 4 <= 0, so for any n>=2:

T(n) <= C (n^2 - 2n + 4) <= C^n^2

And the hypothesis is correct - and by definition of big-O, T(n) is in O(n^2).

Since we have shown T(n) is both in O(n^2) and Omega(n^2), it is also in Theta(n^2)

---

Analyzing recursion is different from analyzing iteration because:

1. n (and other local variable) change each time, and it might be hard to catch this behavior.
2. Things get way more complex when there are multiple recursive calls.