CODEWITHSUNDEEP
javaannotationstime-complexitybig-ocomplexity-theory
Need_MathHelp
Need_MathHelp

Reputation: 121

How to find the time complexity of a recursive method?

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

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

So the problem I am dealing with is how I can write the time complexity of this method using a big O notation.

Here is what I've done so far. I'm not sure if it is correct but let me explain it. I get that T(n)= 2 T(n/2) + 1 for n>4 since we have 2 recursive calls and other operations. But when it comes to n<=4, that is where I got stuck. There is a recursive call which means that even it will be something like T(n)= T(n/2)+1. But this doesn't even feel right, I would really appreciate it if someone could help me.

Upvotes: 1

Views: 67

Answers (1)

Patrick87
Patrick87

Reputation: 28302

Assuming a constant x for our purposes (i.e., we are not interested in the growth rate as a function of x), expIterative is also just a function of n, and is only called for cases where n <= 4. There is some largest time t* that expIterative takes to run on x and n where n goes from 0 to 4. We can simply use that largest time t* as a constant, since the range of n that can be sent as an input is bounded.

double expRecursive(double x, int n) {
    if (n <= 4) {                                       // a+b
        return expIterativ(x, n);                       // c+t*
    }

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

As you pointed out, we can make the simplifying assumption that n is even and just worry about that case. If we assume n is a power of 2, even easier, since then all recursive calls will be for even numbers.

We get

T(n) <= 2T(n/2) + (a+b+2c+d+t*)

The stuff in parentheses at the end is just a sum of constants, so we can add them together and call the result k:

T(n) <= 2T(n/2) + k

We can write out some terms here:

n    T(n)
4    t*
8    2t* + k
16   4t* + 2k + k
32   8t* + 4k + 2k + k
...
2^n  2^(n-2)t* + 2^(n-2)k - k
   = (2^n)(t* + k)/4 - k

So for an input 2^n, it takes time proportional to 2^n. That means that T(n) = O(n).

Upvotes: 1

Related Questions