Calculating time complexity of a recursive algorithm

Question

I'm trying to calculate the time complexity of a recursive algorithm and I think I've almost got it. Here's the psuedocode I've been looking at:

long pow( long x, int n ) {
    if (n == 0)
        return 1;
    if (n == 1)
    return x;
    if(isEven(n))
        return pow(x, n / 2 ) * pow(x, n / 2);
    else
        return x * pow(x * x, n / 2);
}

isEven merely determines whether or not the integer passed to it is even or not, and for the point of this example, operates in constant time.

So, if n = 0 or n = 1, it operates it has constant time operation, like this: f(n) = C0. However, when n > 1, it should operate like so: f(n)= f(n-1) + f(n-1) + C1 when n is even and f(n)= f(n-1) + 1 when n is odd, correct? Or should it be: f(n)= f(n/2) + f(n/2) + C1 when n is even and f(n)= f(n/2) + 1 when n is odd?

I've been looking at a lot of examples. Here is one I've found very helpful. My problem stems from there being two recursive calls when n is even. I'm not fully sure what to do here. If anyone could point me in the right direction I'd really appreciate it.

Is it intentional that you are making two recursive calls to `pow(x, n / 2)` with the same arguments? You could just do `long r = pow(x, n / 2); return r * r;` and then not only is it more efficient, but the analysis is simpler. — kaya3, Jan 26 '20 at 18:53

score 3 · Accepted Answer · answered Feb 01 '11 at 02:43

3

Take a look at the Master Theorem. You can treat this as a "divide and conquer" algorithm.

The end result is that with the two recursive calls in place, you end up with a worst case O(n) runtime. E.g. pow(x, 4) calls pow(x, 2) twice, and pow(x, 1) four times; in general a power of two will result in n*2-1 calls.

Also note that by just calling pow(x, n/2) once and squaring the result in that branch, the algorithm becomes O(log n).

answered Feb 01 '11 at 02:43

Walter Mundt

24,753
5
53
61

Thanks. I've been looking at the Master Theorem a bit and I'm trying to wrap my head around it... guess I'll have to give it a bit more thought! – thomascirca Feb 01 '11 at 02:59
Don't feel too bad -- it's one of the hardest bits you need in the runtime analysis of most common-case code you see. – Walter Mundt Feb 01 '11 at 03:02

score 0 · Answer 2 · answered Feb 01 '11 at 12:57

Let's define f(m) as that it gives you the number of operations of a problem with size m. The 'problem' is of course exponentiation (pow), like x^n or pow(x,n). The long pow( long x, int n ) { function does not need to do more or less work if I change x. So, the size of the problem exponentiation does not depend on x. It does however depend on n. Let's say 2^4 is of size 4 and 3^120 is of size 120. (Makes sense if you see that 2^4=2*2*2*2 and 3^120=3*3*3*3*..*3) The problem size is thus equal to n, the second parameter. We could, if you want, say the problem size is 2*log(n), but that would be silly.

Now we have f(m) is the number of operations to calculate pow(x,m) for any x. Because pow(x,m) is exactly the problem with size m. So, if we have pow(x,y) then the number of operations is, by definition, f(y). For example, pow(3,3*m/2) has f(3*m/2) operations.

Finally, let's count the operations

long pow( long x, int n ) {
    if (n == 0)  //1
        return 1;
    if (n == 1)  //1
    return x;
    if(isEven(n)) //1
        return pow(x, n / 2 ) * //that is f(n/2), y=n / 2
                 pow(x, n / 2); //also f(n/2)
    else
        return x * pow(x * x, n / 2); //1+1+f(n/2)
}

Taking it together: f(n) = 2*f(n/2) + c1 (n even) and f(n) = f(n/2) + c2 (n odd). If you are only interested in the worst case scenario, then note that the odd case is less work. Thus f(n) is bounded above by the even case: f(n) <= 2*f(n/2)+c.

Calculating time complexity of a recursive algorithm

2 Answers2