Writing a recurrence relation for a method

I have a bit of code and need to write a recurrence relation for it. The code simply calculates 2 raised to the nth power. Any help is appreciated.

public static int two(int n) {

     if (n==0) {
       return 1;
     } else if (n%2 == 0) {
       int x = two(n/2);
       return x*x;
     } else { 
       return 2 * two(n-1)
}
开发者_如何转开发

The formulation of the function almost is a recurrence relation. Basically, all you need to do is perform a change of variables so the argument to two in the recursion is n. For example, take the following Fibonacci function:

public static int fib(n) {
    if (n==0) {
        return 1;
    } else if (n==1) {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    }
}

You wouldn't want to use that implementation, since it's horribly inefficient, but it makes writing the recurrence relation easy:

fib0=1
fib1=1
fibn+2 = fibn+1 + fibn

With the fibonacci example, you don't actually need to perform the change of variables. However, with your two function, it will make it simpler to write the relation.

The lines that don't have recursive calls are done in a constant time that we will call c.

T(n)=T(n-1)+c if n is odd.
T(n)=T(n/2)+c if n is even.

After each recursive call with n odd, the next recursive call we be with n-1 even. So in the worst case we start with n odd -> n-1 is even -> (n-1)/2 is odd -> (n-1)/2-1 is even and so on...

If for example we start with n=19 then 19 is odd -> 18 is even -> 9 is odd -> 8 is even -> 4 is even -> 2 is even -> 0.

The depth of the recursive tree is about lgn, and since on each level there are c operations then the running time is clgn=O(lgn).