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)?

Big-O notation only cares about the highest degree. O(n+1) doesn't exist, it's O(n). — Eric, Jul 25 '17 at 17:53
@Eric O(N+1) does exist. Yes O(n+1) is equivalent to O(n) but nothing in the definition of big O specifies that O(n+1) is any less valid a form than O(n). O(n) is obviously just the far more common form because it is convenient. What you are saying is a little like saying 2/4 doesn't exist because its really 1/2. — gbtimmon, Jul 25 '17 at 18:20

Chris Nauroth · Accepted Answer · 2017-07-25T18:06:08.080

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?

score 2 · Answer 2 · answered Jul 25 '17 at 23:58

2

Your pseudocode is still pretty vague as to the exact details of its execution. A more explicit one could be

function factorial1(n) {
    r1 = (n == 1);        // one step
    if r1: { return 1; }  // second step ... will stop only if n==1
    r2 = factorial1(n-1)  // third step ... in addition to however much steps
                          //                it takes to compute the factorial1(n-1)
    r3 = n * r2;          // fourth step
    return r3;
}

Thus we see that computing factorial1(n) takes four more steps than computing factorial1(n-1), and computing factorial1(1) takes two steps:

T(1) = 2
T(n) = 4 + T(n-1)

This translates roughly to 4n operations overall, which is in O(n). One step more, or less, or any constant number of steps (i.e. independent of n), do not change anything.

answered Jul 25 '17 at 23:58

Will Ness

70,110
9
98
181

ah, you are correct. In counting the number of steps, I think you did not count the function call, the if statement and the return statement? Why is that? – lightning_missile Jul 27 '17 at 06:23
1

for `r2 = factorial1(n-1)` I count: whatever number of steps the function call makes, *plus* the assignment. You are right about counting the function call itself: it adds 1 step, the constant number (independent of `n`). So perhaps the total is *8n* - still, O(n). – Will Ness Jul 27 '17 at 07:24
1

On the other hand, it really depends on the implementation. For instance, in assembler, `r1 = (n==1)` could be 1 instruction. For it to be counted as two steps, we would treat the `==1` test as the first step, and `r1 =` assignment as the second step; but in assembler they could both be part of one instruction, because any instruction needs to put its result *somewhere*. But, as you mentioned, this uncertainty can only add constant amount of steps per each *n*, so isn't important for the asymptotic analysis. – Will Ness Jul 27 '17 at 07:29

gbtimmon · Answer 3 · 2017-07-25T19:36:30.493

I would argue that no you would not be correct in saying that.

If something is O(N) then it is by definition O(N+1) as well as O(2n+3) as well as O(6N + -e) or O(.67777N - e^67). We use the simplest form out of convenience for notation O(N) however we have to be aware that it would be true to say that the first function is also O(N+1) and likewise the second is as much O(n) as it wasO(n+1)`.

Ill prove it. If you spend some time with the definition of big-O it isn't too hard to prove that. g(n)=O(f(n)), f(n) = O(k(n)) --implies-> g(n) = O(k(n))

(Dont believe me? Just google transitive property of big O notation). It is then easy to see the below implication follows from the above.

n = O(n+1), factorial1 = O(n) --implies--> factorial1 = O(n+1)

So there is absolutely no difference between saying a function is O(N) or O(N+1). You just said the same thing twice. It is an isometry, a congruency, a equivalency. Pick your fancy word for it. They are different names for the same thing.

If you look at the Θ function you can think of them as a bunch of mathematical sets full of functions where all function in that set have the same growth rate. Some common sets are:

Θ(1)        # Constant 
Θ(log(n))   # Logarithmic
Θ(n)        # Linear
Θ(n^2)      # Qudratic
Θ(n^3)      # Cubic
Θ(2^n)      # Exponential (Base 2)
Θ(n!)       # Factorial

A function will fall into one and exactly one Θ set. If a function fell into 2 sets then by definitions all functions in both sets could be proven to fall into both sets and you really just have one set. At the end of the day Θ gives us a perfect segmentation of all possible functions into set of countably infinite unique sets.

A function being in a big-O set means that it exists in some Θ set which has a growth rate no larger than the big-O function.

And thats why I would say you were wrong, or at least misguided to say it is "more O(N+1)". O(N) is really just a way of notating "The set of all functions that have growth rate equal to or less than a linear growth". And so to say that:

a function is more O(N+1) and less `O(N)`

would be equivalent to saying

a function is more "a member of the set of all functions that have linear
growth rate or less growth rate" and less "a member of the set of all 
functions that have linear or less growth rate"

Which is pretty absurd, and not a correct thing to say.

Big-O is an upper bound, so f(n)=n is in O(n), O(n*n), O(n!), etc. Compare and contrast with big-Θ — rici, Jul 25 '17 at 19:16
Good catch! Counter catch there is no big Θ, just theta ... [O,o,Θ,Ω,ω] :). I'll update the wording in a sec to make it correct. — gbtimmon, Jul 25 '17 at 19:24
That's an unnecessarily confusing way to put it. But technically correct -- so you have that going for you. — gbtimmon, Jul 25 '17 at 19:45

base case and time complexity in recursive algorithms

3 Answers3