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.

Answer 1

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.