Big Oh Notation for a Recursive Algorithm

Question

I have a question that I'm unsure of:

Express the complexity of the following method using big-O notation. You must explain how you arrived at your answer. What value is returned by the call fred(1,4)?

int fred(int x, int y)
{
    if(y == 0)
        return x;
    else if((y % 2) == 0)
        return fred(2 * x, y / 2);
    else
        return fred(x, y / 2);
}

It seems that this would never reach the base case and therefore gets stuck in an infinite loop. Am I correct here? Do functions like this have an answer for complexity like O(infinity)?

Answer 1

An algorithm is called algorithm because it always converges. You will see in this simple function $y$ is always decreasing and eventually obtains zero and then the algorithm terminates. In this case,

fred(1,4)=fred(2,2)=fred(4,1)=fred(4,0)=4

To analyse the complexity of the algorithm, note that y reaches its half each iteration so it belongs to $O(\log y)$.