Confusion in the concept of constant time/space complexity

Question

I am confused with the concept of constant time/space complexity.

For example:

public void recurse(int x) {
    if(x==0) return;
    else recurse(x/10);
}

where, 1<x<=2147483647

If we want to express the space complexity for this function in terms of big O notation and count the stack space for recursion, what will be the space complexity?

I am confused between:

1. O(1) - The maximum value of int in java is 2147483647, so at max it will recurse 10 times.
2. O(log x) - Number of recursions is really dependent on the number of digits in x, so at max we will have ~log₁₀x recursion.

If we say it is O(1), then wouldn't any algorithm which has some finite input can have its time/space complexity bounded by some number? So let's take case of insertion sort in an array of numbers in java. The largest array you can have in java is of size 2147483647, so does that mean T(n) = O(2147483647²) = O(1)?

Or should I just look it as, O(1) is a loose bound, while O(log x) is a tighter bound?

Here is the definition I found on wikipedia:

An algorithm is said to be constant time (also written as O(1) time) if the value of T(n) is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an array takes constant time as only one operation has to be performed to locate it. In a similar manner, finding the minimal value in an array sorted in ascending order; it is the first element. However, finding the minimal value in an unordered array is not a constant time operation as scanning over each element in the array is needed in order to determine the minimal value. Hence it is a linear time operation, taking O(n) time. If the number of elements is known in advance and does not change, however, such an algorithm can still be said to run in constant time.

Answer 1

When your algo doesnt depend on size of input, it is said to have constant time complexity. For eg:

function print(int input) {
  // 10 lines of printing here

}

Here, no matter what you pass in as 'input', function body statements will always run 10 times. If you pass 'input' as 10, 10 statements are run. If you pass 'input' as 20, still 10 statements are run.

Now on other hand, consider this:

function print(int input) {

  // This loop will run 'input' times
  for(int i=0;i<input;i++){
      System.out.println(i);
   }

}

This algo will run depending on the size of input. If you pass 'input' as 10, for loop will run 10 times, If you pass 'input' as 20, for loop will run 20 times. So, algo grows with the same pace as 'input' grows. So, in this case time complexity is said to be O(n)

Answer 2

Applying asymptotic complexity to the real world is tricky as you have discovered.

Asymptotic complexity deals with the abstract situation where input size N has no upper limit, and you're only interested in what will happen with arbitrarily large input size.

In the real world, in the practical applications you're interested, the input size often has an upper limit. The upper limit may come from the fact that you don't have infinite resources (time/money) to collect data. Or it may be imposed by technical limitations, like the fixed size of int datatype in Java.

Since asymptotic complexity analysis does not account for real world limitations, the asymptotic complexity of recurse(x) is O(log x). Even though we know that x can only grow up to 2^31.

Answer 3

It really depends on why you are using the big-O notation.

You are correct in saying that, technically, any algorithm is O(1) if it only works for a finite number of possible inputs. For example, this would be an O(1) sorting algorithm: "Read the first 10^6 bits of input. If there are more bits left in the input, output "error". Otherwise, bubblesort."

But the benefit of the notation lies in the fact that it usually approximates the actual running time of a program well. While an O(n) algorithm might as well do 10^100 * n operations, this is usually not the case, and this is why we use the big-O notation at all. Exceptions from this rule are known as galactic algorithms, the most famous one being the Coppersmith–Winograd matrix multiplication algorithm.

To sum up, if you want to be technical and win an argument with a friend, you could say that your algorithm is O(1). If you want to actually use the bound to approximate how fast it is, what you should do is imagine it works for arbitrarily large numbers and just call it O(log(n)).

Side note: Calling this algorithm O(log(n)) is a bit informal, as, technically, the complexity would need to be expressed in terms of size of input, not its magnitude, thus making it O(n). The rule of thumb is: if you're working with small numbers, express the complexity in terms of the magnitude - everyone will understand. If you're working with numbers with potentially millions of digits, then express the complexity in terms of the length. In this case, the cost of "simple" operations such as multiplication (which, for small numbers, is often considered to be O(1)) also needs to be factored in.

Answer 4

When analysing the time and space complexity of algorithms, we have to ignore some limitations of physical computers; the complexity is a function of the "input size" n, which in big O notation is an asymptotic upper bound as n tends to infinity, but of course a physical computer cannot run the algorithm for arbitrarily large n because it has a finite amount of memory and other storage.

So to do the analysis in a meaningful way, we analyse the algorithm on an imaginary kind of computer where there is no limit on an array's length, where integers can be "sufficiently large" for the algorithm to work, and so on. Your Java code is a concrete implementation of the algorithm, but the algorithm exists as an abstract idea beyond the boundary of what is possible in Java on a real computer. So running this abstract algorithm on an imaginary computer with no such limits, the space complexity is O(log n).

This kind of "imaginary computer" might sound a bit vague, but it is something that can be mathematically formalised in order to do the analysis rigorously; it is called a model of computation. In practice, unless you are doing academic research then you don't need to analyse an algorithm that rigorously, so it's more useful to get comfortable with the vaguer notion that you should ignore any limits which would prevent the algorithm running on an arbitrarily large input.

Answer 5

Constant time or space means that the time and space used by the algorithm don't depend on the size of the input.

A constant time (hence O(1)) algorithm would be

public int square(int x){
    return x * x;
}

because for any input, it does the same multiplication and it's over.

On the other hand, to sum all elements of an array

public int sum(int[] array){
    int sum = 0;
    for(int i : array) sum += i;
    return sum;
}

takes O(n) time, where n is the size of the array. It depends directly on the size of the input.

The space complexity behaves equally.

Any thing that doesn't rely on the size of any input is considered constant.