base case and time complexity in recursive algorithms

Question

I would like some clarification regarding O(N) functions. I am using SICP.

Consider the factorial function in the book that generates a recursive process in pseudocode:

function factorial1(n) {
    if (n == 1) {
        return 1;
    }
    return n*factorial1(n-1);
}

I have no idea how to measure the number of steps. That is, I don't know how "step" is defined, so I used the statement from the book to define a step:

Thus, we can compute n ! by computing (n-1)! and multiplying the result by n.

I thought that is what they mean by a step. For a concrete example, if we trace (factorial 5),

• factorial(1) = 1 = 1 step (base case - constant time)
• factorial(2) = 2*factorial(1) = 2 steps
• factorial(3) = 3*factorial(2) = 3 steps
• factorial(4) = 4*factorial(3) = 4 steps
• factorial(5) = 5*factorial(4) = 5 steps

I think this is indeed linear (number of steps is proportional to n).

On the other hand, here is another factorial function I keep seeing which has slightly different base case.

function factorial2(n) {
    if (n == 0) {
        return 1;
    }
    return n*factorial2(n-1);
}

This is exactly the same as the first one, except another computation (step) is added:

• factorial(0) = 1 = 1 step (base case - constant time)
• factorial(1) = 1*factorial(0) = 2 steps
• ...

Now I believe this is still O(N), but am I correct if I say factorial2 is more like O(n+1) (where 1 is the base case) as opposed to factorial1 which is exactly O(N) (including the base case)?

Answer 1

One thing to note is that factorial1 is incorrect for n = 0, likely underflowing and ultimately causing a stack overflow in typical implementations. factorial2 is correct for n = 0.

Setting that aside, your intution is correct. factorial1 is O(n) and factorial2 is O(n + 1). However, since the effect of n dominates over constant factors (the + 1), it's typical to simplify it by saying it's O(n). The wikipedia article on Big O Notation describes this:

...the function g(x) appearing within the O(...) is typically chosen to be as simple as possible, omitting constant factors and lower order terms.

From another perspective though, it's more accurate to say that these functions execute in pseudo-polynomial time. This means that it is polynomial with respect to the numeric value of n, but exponential with respect to the number of bits required to represent the value of n. There is an excellent prior answer that describes the distinction.

What is pseudopolynomial time? How does it differ from polynomial time?