Running time complexity of the function

Question

I need to find the running time complexity of this recursive function

int f3(int i, int j)
{
    if (i < 10)
    {
        return i;
    }
    else if (i < 100)
    {
        return f3(i - 2, j);
    }
    else
    {
        return f3(i / 2, j);
    }
}

Is it O(logn) or O(n)? From my understanding since it divides the number by two growth rate of the number of calls with higher n is not linear but logarithmic. But the running time also depends on how big n is so I am not sure what is the correct answer.

Answer 1

You are right in that for large values of i, i gets halved at each recursive call. Each call also does only constant work. This is the important concept.

In big-O analysis, we only care about the growth rate of the function. It does not matter that for i < 100, the function takes "linear" time, as in the grand scheme of things, this is a constant amount of work for i < 100.

Another way to see this is that we can represent the running time of this algorithm with a recurrence.

For i >= 100, i gets halved and the function only does constant work. For i < 100, we can consider it as constant amount of work. So we have:

T(i) = O(1)             if i < 100
T(i) = T(i/2) + O(1)    otherwise

The solution to this is O(log(i)).