Determining complexity for recursive functions (Big O notation)

big-o, complexity-theory, recursion

Solution

The time complexity, in Big O notation, for each function:

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

This function is being called recursively n times before reaching the base case so its `O(n)`, often called linear.

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

This function is called n-5 for each time, so we deduct five from n before calling the function, but n-5 is also `O(n)`. (Actually called order of n/5 times. And, O(n/5) = O(n) ).

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

This function is log(n) base 5, for every time we divide by 5 before calling the function so its `O(log(n))`(base 5), often called logarithmic and most often Big O notation and complexity analysis uses base 2.

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

Here, it's `O(2^n)`, or exponential, since each function call calls itself twice unless it has been recursed n times.

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

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

And here the for loop takes n/2 since we're increasing by 2, and the recursion takes n/5 and since the for loop is called recursively, therefore, the time complexity is in

(n/5) * (n/2) = n^2/10,

due to Asymptotic behavior and worst-case scenario considerations or the upper bound that big O is striving for, we are only interested in the largest term so `O(n^2)`.

Good luck on your midterms ;)

Problem

I have a Computer Science Midterm tomorrow and I need help determining the complexity of these recursive functions. I know how to solve simple cases, but I am still trying to learn how to solve these harder cases. These were just a few of the example problems that I could not figure out. Any help would be much appreciated and would greatly help in my studies, thank you! ``` int recursiveFun1(int n) { if (n <= 0) return 1; else return 1 + recursiveFun1(n-1); } int recursiveFun2(int n) { if (n <= 0) return 1; else return 1 + recursiveFun2(n-5); } int recursiveFun3(int n) { if (n <= 0) return 1; else return 1 + recursiveFun3(n/5); } void recursiveFun4(int n, int m, int o) { if (n <= 0) { printf("%d, %d\n",m, o); } else { recursiveFun4(n-1, m+1, o); recursiveFun4(n-1, m, o+1); } } int recursiveFun5(int n) { for (i = 0; i < n; i += 2) { // do something } if (n <= 0) return 1; else return 1 + recursiveFun5(n-5); } ```

Original source

Related problems