By Michael_19


2012-11-20 06:28:37 8 Comments

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

3 comments

@Shubham 2017-05-16 01:29:31

One of the best ways I find for approximating the complexity of the recursive algorithm is drawing the recursion tree. Once you have the recursive tree:

Complexity = length of tree from root node to leaf node * number of leaf nodes
  1. The first function will have length of n and number of leaf node 1 so complexity will be n*1 = n
  2. The second function will have the length of n/5 and number of leaf nodes again 1 so complexity will be n/5 * 1 = n/5. It should be approximated to n

  3. For the third function, since n is being divided by 5 on every recursive call, length of recursive tree will be log(n)(base 5), and number of leaf nodes again 1 so complexity will be log(n)(base 5) * 1 = log(n)(base 5)

  4. For the fourth function since every node will have two child nodes, the number of leaf nodes will be equal to (2^n) and length of the recursive tree will be n so complexity will be (2^n) * n. But since n is insignificant in front of (2^n), it can be ignored and complexity can be only said to be (2^n).

  5. For the fifth function, there are two elements introducing the complexity. Complexity introduced by recursive nature of function and complexity introduced by for loop in each function. Doing the above calculation, the complexity introduced by recursive nature of function will be ~ n and complexity due to for loop n. Total complexity will be n*n.

Note: This is a quick and dirty way of calculating complexity(nothing official!). Would love to hear feedback on this. Thanks.

@Ben Forsrup 2018-01-29 15:16:15

Excellent answer! I have a question on the fourth function. If it would have had three recursive calls, would the answer be (3^n). Or would you still just say (2^n)?

@Julian A. 2018-02-25 20:55:57

@Shubham: #4 doesn't seem right to me. If the number of leaves is 2^n then the height of the tree must be n, not log n. The height would only be log n if n represented the total number of nodes in the tree. But it doesn't.

@Shubham 2018-03-01 00:41:37

@BenForsrup: It will be 3^n because every node will have three child nodes. Best way to be sure about this is to draw the recursive tree yourselves with dummy values.

@Fintasys 2019-05-28 14:54:03

#2 should be n-5 not n/5

@coder 2012-11-20 06:37:40

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

  1. The first function is being called recursively n times before reaching base case so its O(n), often called linear.
  2. The second 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) ).
  3. 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.
  4. In the fourth, it's O(2^n), or exponential, since each function call calls itself twice unless it has been recursed n times.
  5. As for the last function, the for loop takes n/2 since we're increasing by 2, and the recursion take n-5 and since the for loop is called recursively therefore the time complexity is in (n-5) *(n/2) = (2n-10) * n = 2n^2- 10n, 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 ;)

@coder 2012-11-20 07:19:41

your right about the fifth, the n will decrease for the for loop but for the fourth I don't think its n^2 for its like a tree each time your calling the recursion twice so it should be 2^n plus that was your answer in the comment earlier.

@nhahtdh 2012-11-20 07:26:37

Yes, the 4th one is 2^n, my deleted comment has a typo. But you should fix your post since it is saying log(2^n)

@coder 2012-11-20 07:30:24

oh, seriously I didn't notice it, thank u, truly I wrote the log by mistake :$

@Gwater17 2017-03-04 01:48:26

Can someone explain the last one in more detail? I get that the recursiveFunc5 is 1/5 * n like problem 2 and I get that the loop is 1/2 * n. Since the loop runs for every recursive call I thought the answer would be (1/5n ^ 1/2n) and since coefficients are dropped it'd ultimately be n^n

@bjc 2017-09-14 09:08:56

@MJGwater Let the running time of the loop is m. When the recursive run 1 time, it takes m to execute the loop. When the recursive run 2 times, the loop is also run 2 times, so it takes 2m... and so on. So it's '*', not '^'.

@Stanislav Iegorov 2019-02-04 19:51:32

I think the fifth point should be (n-5) * (n/2) = (n^2 - 5n) / 2 which still leads to O(n^2)

@Ridhwaan Shakeel 2019-03-14 00:11:43

For #4, is O(n^2) the worst case, considering it makes two recursive calls end-to-end unless it wasnt recursed n times?

@coder 2019-03-14 13:42:04

@RidhwaanShakeel No there is no best case and worst case in the fourth question since n is not affected by any factor it is only decremented by one recursively. so each time it enters the loop it will call itself twice, if n = 5 then it will call itself 2^5, you can try to draw it as a tree so you may visualize. I hope this makes clear.

@Jack 2019-04-17 17:28:12

@coder The explanation for 5 seems odd. If incrementing by 2 results in n/2 iterations of the for loop, why would decrementing by 5 not result in n/5 recursive calls? This would still result in O(n^2) but seems like a more intuitive explanation. Why mix subtraction and division when they're essential doing the same thing?

@nhahtdh 2012-11-20 07:55:00

For the case where n <= 0, T(n) = O(1). Therefore, the time complexity will depend on when n >= 0.

We will consider the case n >= 0 in the part below.

1.

T(n) = a + T(n - 1)

where a is some constant.

By induction:

T(n) = n * a + T(0) = n * a + b = O(n)

where a, b are some constant.

2.

T(n) = a + T(n - 5)

where a is some constant

By induction:

T(n) = ceil(n / 5) * a + T(k) = ceil(n / 5) * a + b = O(n)

where a, b are some constant and k <= 0

3.

T(n) = a + T(n / 5)

where a is some constant

By induction:

T(n) = a * log5(n) + T(0) = a * log5(n) + b = O(log n)

where a, b are some constant

4.

T(n) = a + 2 * T(n - 1)

where a is some constant

By induction:

T(n) = a + 2a + 4a + ... + 2^n * a + T(0) * 2 ^ n 
     = a * 2^(n+1) - a + b * 2 ^ n
     = (2 * a + b) * 2 ^ n - a
     = O(2 ^ n)

where a, b are some constant.

5.

T(n) = n / 2 + T(n - 5)

We can prove by induction that T(5k) >= T(5k - d) where d = 0, 1, 2, 3, 4

Write n = 5m - b (m, b are integer; b = 0, 1, 2, 3, 4), then m = (n + b) / 5:

T(n) = T(5m - b) <= T(5m)

(Actually, to be more rigorous here, a new function T'(n) should be defined such that T'(5r - q) = T(5r) where q = 0, 1, 2, 3, 4. We know T(n) <= T'(n) as proven above. When we know that T'(n) is in O(f), which means there exist constant a, b so that T'(n) <= a * f(n) + b, we can derive that T(n) <= a * f(n) + b and hence T(n) is in O(f). This step is not really necessary, but it is easier to think when you don't have to deal with the remainder.)

Expanding T(5m):

T(5m) = 5m / 2 + T(5m - 5) 
      = (5m / 2 + 5 / 2) * m / 2 + T(0) 
      = O(m ^ 2) = O(n ^ 2)

Therefore, T(n) is O(n ^ 2).

@Dimitar Dimitrov 2013-09-03 04:18:07

I recently failed an interview question (and by extend the interview) that has to do with analyzing the time and space complexity of a recursive fibonacci function. This answer is epic and it helped a lot, I love it, I wish I could up vote you twice. I know it's old but do you have anything similar for calculating space - maybe a link, anything ?

Related Questions

Sponsored Content

39 Answered Questions

27 Answered Questions

[SOLVED] What is tail recursion?

23 Answered Questions

[SOLVED] Big O, how do you calculate/approximate it?

11 Answered Questions

[SOLVED] Computational complexity of Fibonacci Sequence

9 Answered Questions

[SOLVED] How to find time complexity of an algorithm

1 Answered Questions

complexity for recursive functions (Big O notation)

1 Answered Questions

[SOLVED] How do I calculate big O notation for my recursive function?

  • 2017-10-27 04:54:42
  • FatimahFatCakes
  • 365 View
  • 0 Score
  • 1 Answer
  • Tags:   java recursion big-o

1 Answered Questions

[SOLVED] Big O of recursive functions with multiple function calls?

Sponsored Content