Big o notation and recursive functions

Question

I am trying to learn Big-O notation but i have difficulties in calculating time complexity of recursive functions.

Can you help me to understand the time complexity of following example?

public int recursiveFunction(int n) {
    if (n == 0) {
        return 0;
    }

    return Math.max(recursiveFunction(rand(n)) + 2,recursiveFunction(n - 1));
}

public int rand(int n) {
    return new Random().nextInt(n - 1);
}

Thanks.

The result of your function is a *stack overflow* (and it is not a valid Java code) — Kru, Jan 02 '13 at 13:33
... and the theoretical complexity is O(∞). You recur unconditionally, you have no base case. — Marko Topolnik, Jan 02 '13 at 13:34
I know it is not a valid java code. It is something like pseudo code. I just want to learn the analysis. — user987654, Jan 02 '13 at 13:35
updated code. result is not important.I just want to know that how many times does it run and what will be the time complexity. — user987654, Jan 02 '13 at 13:39

score 5 · Answer 1 · answered Jan 02 '13 at 14:18

The time will depend on what rand(n) returns, but if you take the worst-case, this will be n-2. So the code simplifies to:

public int recursiveFunction(int n) {
    if (n == 0) {
        return 0;
    }

    return Math.max(recursiveFunction(n - 2) + 2,recursiveFunction(n - 1));
}

which has an asymptotic upper bound equal to that of:

public int recursiveFunction(int n) {
    if (n == 0) {
        return 0;
    }

    recursiveFunction(n-1);
    recursiveFunction(n-1);

    return 0;
}

which is a recursion with a depth of n and a branch factor of 2, so O(2^n) time-complexity.

score 3 · Answer 2 · edited May 23 '17 at 12:18

3

Recursive functions is not a good place to start learning about complexity. Even a relatively simple recursive function can require quite complex calculations to determine complexity.

For recursiveFunction(n), you call recursiveFunction(n-1) and recursiveFunction(a) where a < n-1, so at worst that is recursiveFunction(n-1) once and recursiveFunction(n-2) once. That has the same complexity as a Fibonacci series, it's complexity is O(2^n). You'll note the algorithm in the link looks very similar to yours.

edited May 23 '17 at 12:18

Community

1
1

answered Jan 02 '13 at 14:14

Bernhard Barker

54,589
14
104
138

Thanks for your response. I know the simple calculations,but it is hard to understand the one with recursive functions. – user987654 Jan 02 '13 at 14:21

score 0 · Answer 3 · answered Jan 02 '13 at 14:20

You have no understood the problem of your code. Because your code creates random values its runtime complexity cannot be determined. Because of your '+2' and '-1' it is also possible for the program to never end. However, this is not likely but possible, thus one can only say it is O(infinite).

Usual cases of the bigO notation:

You have only one loop:

for(int k=0;k<n;++k) {}

this comes to O(n), because you have n iterations

Two or more loops in sequence:

for(int k=0;k<n;++k) {}
for(int l=0;l<n;++l) {}

comes to O(2*n), but constants do not matter on bigO, so it is O(n)

Entangled loops:

for(int k=0;k<n;++k) {
    for(int l=0;l<n;++l) {
    }
}

is O(n²),

for(int k=0;k<n;++k) {
    for(int l=0;l<n;++l) {
        for(int m=0;m<n;++m) {
        }
    }
}

is O(n³) and so on

And the most common complexity you will encounter for search/comparison algorithms is

for(int k=0;k<n;++k) {
    for(int l=k;l<n;++l) {// note here: l=k instead of l=0
    }
}

Is O(n*log(n))

For more details use google.

1

(1) `for(int k=0;k – Bernhard Barker Jan 02 '13 at 14:29

score 0 · Answer 4 · answered Mar 23 '14 at 09:10

You picked a rather tricky problem here. The calculation with Math.Max doesn't matter much, what matters is the two recursive calls.

There's a problem here when n == 1 because you call rand (1), which calls Random().nextInt (0) which is not defined - it is supposed to return a random integer which is >= 0 and < 0 which is not possible. Let's hope it returns 0 - if not, we are in trouble.

recursiveFunction (n) calls recursiveFunction (n - 1), and makes another call recursiveFunction (i) with a random i, 0 <= i <= n - 2. Let's make a table of the maximum number of calls that are made, counting 1 for the initial call (assuming rand (1) returns 0, and every other call returns n - 2):

n = 0: 1 calls
n = 1: 1 + 1 + 1 = 3 calls
n = 2: 1 + 1 + 3 = 5 calls
n = 3: 1 + 3 + 5 = 9 calls
n = 4: 1 + 5 + 9 = 15 calls
n = 5: 1 + 9 + 15 = 25 calls
n = 6: 1 + 15 + 25 = 41 calls
n = 7: 1 + 25 + 41 = 67 calls
n = 8: 1 + 41 + 67 = 109 calls
n = 9: 1 + 67 + 109 = 177 calls
n = 10: 1 + 109 + 177 = 287 calls

The number of calls grow fast, but not quite as fast as 2^n. I'd say it is O (c^n) with c = sqrt (1.25) + 0.5. That's the worst case; average is a lot less.

Big o notation and recursive functions

4 Answers4