computer science - What does "in constant time" imply?

Question

I work as a programmer, but have no computer science background, so recently I've been following along with the excellent MIT OpenCourseWare intro to Computer Science and Programming. In the course of which, the question is asked: "will any program written using only function definitions and calls, the basic arithmetic operators, assignment and conditionals run in constant time?"

I thought the answer was yes, since all of these operations seem pretty simple. But as you smart people probably already knew, the correct answer was no, apparently because of the potential for indefinite recursion.

It seems like I just don't understand the implications of "in constant time". The way I pictured the meaning, it sounded like it just meant that a simple operation would take a known amount of time to complete. I accept that recursion can lead to your program running forever, but aren't the individual operations still taking a finite and measurable amount of time each... even if there are now an infinite number of them? Or does the answer just mean that two infinitely recursive programs cannot validly be said to take the same amount of time to run?

If anyone can give me an authoritative definition of "in constant time", and the implications thereof, I'd be very grateful!

Answer 1

Constant time effectively means you can give a constant upper bound to how long the program will take to run which isn't affected by any of the input parameters.

Compare that with, say, linear time (for some input n - which will often actually be the size of the input data rather than a direct value) - which means that the upper bound of the time taken can be expressed as mn + k for some values of m and k.

Note that it doesn't mean a program will take the same amount of time for any input data just because it runs in constant time. For example, consider this method:

int foo(int n)
{
    if (n == 0)
    {
        return 0;
    }
    int j = n + 1;
    int k = j * 2;
    return k;
}

That's doing more work in the case where n is non-zero than in the case where it's zero. However, it's still constant time - at most, it's going to do one comparison, one addition, and one multiplication.

Now compare that with a recursive function:

public int foo(int n)
{
    if (n <= 1)
    {
        return 1;
    }
    return n * foo(n - 1);
}

This will recurse n times - so it's linear in n. You can get much worse than linear, however. Consider this method for computing a Fibonacci number:

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

That doesn't look much worse than the previous version - but this is now exponential (the upper bound is most easily expressed in terms as O(2ⁿ). It's still only using simple comparisons, addition, and function calls though.