Time-Complexity of recursive function

Question

I'm having some trouble determining the time complexity of this recursive function in terms of Big-O notation.

double expRecursive(double x, int n) {
    if (n <= 4) {
        return expIterativ(x, n);
    }

    return expRecursive(x, n/2) *
           expRecursive(x, (n + 1)/2);
}

(The time complexity of the method expIterative is O(n))

Is the recurrence relation of expRecursive() T(n) = 2T(n/2) + n?

If this is the case I suppose T(n) = O(nlogn) after applying the master theorem?

My biggest problem is coming up with the correct recurrence relation...

Are you asking about how long it takes to run, or how big its output is? — Louis Wasserman
Welcome to SO! Looks like O(log(n)) to me but it's rather ambiguous because expIterativ's behavior on negative numbers is unclear. If it only does work from 0 < n <= 4 then it's constant time and you're left with 2*log(n) == O(log(n)). I assume this function is always called with positive numbers. — ggorlen
Ok, thanks! Yes, expIterative only works for n >= 0. But I still can't understand how to make a recurrence relation T(n) = aT(n/b) + n^c with expRecursive. — TheCoder
Can someone help me to understand how to write the recurrence relation T(n) = aT(n/b) + n^c? :) — TheCoder

Mo B. Mo B. · Accepted Answer · 2021-01-21T09:19:22

To get the recurrence relation, it helps to first annotate the code:

double expRecursive(double x, int n) {
    if (n <= 4) {
        return expIterativ(x, n);       // O(1) since n is bounded
    }

    return expRecursive(x, n/2)         // T(n/2)
           *                            // O(1)
           expRecursive(x, (n + 1)/2);  // T(n/2)
}

So the recurrence relation is

T(n) = O(1),              for 0 <= n <= 4
T(n) = 2 * T(n/2) + O(1), for n > 4

which has the solution T(n) ∈ Ө(n).

Time-Complexity of recursive function

1 Answers