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

i work programmer, have no computer science background, i've been following along excellent mit opencourseware intro computer science , programming. in course of which, question asked: "will program written using function definitions , calls, basic arithmetic operators, assignment , conditionals run in constant time?"

i thought answer yes, since of these operations seem pretty simple. smart people knew, correct answer no, apparently because of potential indefinite recursion.

it seems don't understand implications of "in constant time". way pictured meaning, sounded meant simple operation take known amount of time complete. accept recursion can lead program running forever, aren't individual operations still taking finite , measurable amount of time each... if there infinite number of them? or answer mean 2 infinitely recursive programs cannot validly said take same amount of time run?

if can give me authoritative definition of "in constant time", , implications thereof, i'd grateful!

constant time means can give constant upper bound how long program take run isn't affected of input parameters.

compare with, say, linear time (for input n - size of input data rather direct value) - means upper bound of time taken can expressed mn + k values of m , k.

note doesn't mean program take same amount of time input data because runs in constant time. example, consider 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 case n non-zero in case it's zero. however, it's still constant time - at most, it's going 1 comparison, 1 addition, , 1 multiplication.

now compare recursive function:

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

this recurse n times - it's linear in n. can worse linear, however. consider method computing 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 worse previous version - exponential (the upper bound expressed in terms o(2ⁿ). it's still using simple comparisons, addition, , function calls though.