CODEWITHSUNDEEP
javarecursionbig-otime-complexity
user987654
user987654

Reputation: 41

Big o notation and recursive functions

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.

Upvotes: 3

Views: 2105

Answers (4)

gnasher729
gnasher729

Reputation: 52538

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.

Upvotes: 0

JayC667
JayC667

Reputation: 2576

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.

Upvotes: 0

fgb
fgb

Reputation: 18569

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.

Upvotes: 5

Bernhard Barker
Bernhard Barker

Reputation: 55589

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.

Upvotes: 3

Related Questions