Measuring time complexity in the length of the input v/s in the magnitude of the input

Question

I know that formally the time compliexity of an algorithm is measured in the length of the input, which in binary would be the number of bits required to encode the input.

The problem that I have with this definition is that wouldn't this definition make a lot of seemingly obvious poly-time algorithms involving numbers exponential time?

For example, consider the algorithm of listing all integers between 1 and another integer n. The algorithm would be a simple loop, listing a number in each iteration from 1 to n. This loop would have $n$ iterations and would thus take $O(n)$ time.

Now if $n$ is encoded in $b$ bits then $b = \lg n \implies 2^b = n \implies$ in the length of the input the algorithm is $O(2^b)$ which is exponential, which is very unintuitive because the loop, in each iteration, does constant amount of work and there are $n$ iterations in total.

By the same logic, consider a loop that prints Hello World $n$ times, where $n$ is an integer, then by the same procedure as above, this algorithm would also be exponential time in the length of the input $n$.

What am I missing?

Answer 1

You're not missing anything -- you are correct!

Consider a loop that prints Hello World $n$ times, where $n$ is an integer, then by the same procedure as above, this algorithm would also be exponential time in the length of the input $n$.

Correct. This is an exponential time algorithm.

If it helps, remember that in most programming languages, integers are represented in binary. If the integer is $32$-bits long, that means the loop might run up to $2^{32} = 4294967296$ times! That's a rather long time. If I use 64-bit integers or big integers, the running time could be far worse.

Now if $n$ is encoded in $b$ bits then $b = \lg n \implies 2^b = n \implies$ in the length of the input the algorithm is $O(2^b)$ which is exponential, which is very unintuitive because the loop, in each iteration, does constant amount of work and there are $n$ iterations in total.

What you're getting at here is that it's important to distinguish your variables when using big-oh notation. Whenever I say "linear time" or "exponential time", really we should be more precise: linear in what variable? Exponential in what variable? In your case, the algorithm is exponential in $b$, but linear in $n$. That is, the algorithm is:

• Exponential in the size of the input

• Linear in the value of the input

and both of these statements are simultaneously true!

When we don't specify the variable, we usually mean in the size of the input, so we would use the first statement. But the second statement is also sometimes useful. For example, if this loop is embedded in a larger program where $n$ is the length of a list $L$, then the loop would be linear in the size of the input (i.e., linear in the size of $L$).

---

Edit: Why is this useful?

The short answer is because "length of the input" is the most general way to describe complexity that isn't specific to a particular type. For example, if we have a sorting algorithm on lists, $f: \text{List} \to \text{List}$, it wouldn't make sense to say $f$ is linear (or quadratic or exponential) in the value of its argument. So by default, we always use the length of the input to describe complexity in a generic way.

Additionally, it turns out that this type of complexity is more compositional. Using the length of the input as the parameter, we can prove, for instance, that the composition of two linear algorithms is linear, and that the composition of two polynomial algorithms is polynomial.

However, you're free to describe algorithms on integers in terms of the value of the input -- there's nothing wrong with that! You just have to be clear to specify so that there's no confusion.

Answer 2

@CalebStanford's answer is excellent, but just to add one point:

There is a distinction between how many operations are needed and how many bits are needed (more for each number of many digits), and the latter introduces an extra $O(\log n)$ factor because$$\sum_{i=1}^bi2^{i-1}\sim b2^b\sim n\log_2n$$for $2^{n-1}\le b\le2^n-1$. This $O(n\log n)$ behaviour is a linearithmic bit complexity, even though the operation complexity is linear in $n$. Both are exponential in $b$ because$$n\log n\sim b2^b=2^{b+\log_2b}\in o(3^b)\setminus O(2^b).$$ But in terms of $n$, where the $\log n$ factor affects classification, which complexity measure does one call "time complexity"? As explained here, at least one version of the sieve of Eratosthenes for finding primes up to $n$ needs $O(n\log\log n)$ operations but has bit complexity $O(n\log n\log\log n)$. They prefer to apply the term "time complexity" to the former.

Depending on the context, this distinction can be more important, not to mention warranting fussier questions about how you count operations. Famously, bit complexity must be at least big-O of space complexity, but operation complexity might not be. For example, how quickly can you compute the $n$th Fibonacci number? There's a technique that takes $O(\log n)$ matrix multiplication operations, but $F_n$ has $O(n)$ digits, so just writing down the value when you know it has linear bit complexity. What's more, the matrix entries end up eventually having $O(n)$ digits too, which eventually slows down the arithmetic operations subsumed into the latest matrix multiplication operation.

Answer 3

There are two good answers already, but there are two points that weren't touched on. One is that of output-polynomial time. A lot of theoretical CS concerns itself purely with decision problems, where the output is just a single bit; these are languages Sometimes instead you want a whole many-bit output, like multiplying two matrices; these are function problems.

Both of the examples you gave (outputting "Hello world" n times, or printing out 1 through n) have a very large output. Since there are plenty of problems where the desired output is very large, it can be valuable to turn the attention from "How long does it take my code to run" to "How long does it take per byte of output?". If I can generate the next byte of output in polynomial time, then it's "output-polynomial time" algorithm.

For example, if you want me to enumerate all the permutations from 1 to 10, I'll have 10! permutations to output. A naive algorithm might start with [1,1,1,1,1,1,1,1,1,1], recognize that it's not a permutation, and move on to [1,1,1,1,1,1,1,1,1,2], and so on. When it reaches [1,2,3,4,5,6,7,8,9,10], it will output that, then move on to [1,2,3,4,5,6,7,8,10,1] and so on. For permutations of 1 to n, this takes $n^n$ time, as compared to the $n! \approx (n/e)^n$ output size. Thus this runs in approximately $S^{1 + \frac{1}{\log(n)}} < S^1.1$ time, and is output-polynomial. Smarter enumeration algorithms can do it in $Sn$ time, which only has polynomial overhead (in $n$) over the output size. This so-called "output-sensitive analysis" is useful when the size of the output might not be easily known ahead of time. This paper is an example of recent work of this type: given points in a plane, connect them into a non-self-intersecting polygon. It's easy to find one way, and there may be very few ways or very many ways (like $n!$ many). An $n!$ algorithm is no good if there's actually only, say, 3 solutions to print out, so we want something that scales with the output size.

The other thing I wanted to mention is the importance of unary encoding in complexity theory. In very precise (that is, very mathematician-oriented) definitions of some problems, authors will specify that some input number $k$ must be specified in unary. This way, an algorithm will be polynomial time if it runs in $poly(k)$, as opposed to needing to run in $poly(2^k)$ (which it would need to do if $k$ was in binary). For example, SUBSET-SUM can be solved in polynomial time, if all the numbers are written in unary.

Answer 4

You are correct; time complexity in theoretical computer science is usually measured in terms of the size of the input¹.

This imposes a wrinkle for working programmers using time complexity to reason about their algorithms' performance. As you note, a lot of operations on numbers have higher complexity than a programmer would expect because numbers of high magnitude can be represented in a small amount of space and CPUs implement basic operations as single instructions. To a programmer, comparing two integers for equality is a (very cheap) constant time operation. To a computer scientist it requires linear time (in the size of the representation of the integers, not in their magnitude)!

But the basic idea of using big-oh complexity to measure running time fundamentally relies on inputs being arbitrarily large, and even the basic theoretical notions of whether problems are computable or not relies on the input space being infinite. Whereas the way primitive numeric types work in actual CPUs relies on them being fixed-size units that therefore have a bounded size and a finite number of possible values.

In big-oh complexity analysis we're giving an expression that will bound the runtime as inputs grow arbitrarily large. If the input is a single number expressed in a primitive machine type, the largest possible input is a constant, and thus the largest possible runtime is also a constant. Many problems would thus have "degenerate" $O(1)$ runtime if analysed this way. Additionally every problem that has only a finite number of cases is decidable, because a big (but finite) mapping table would decide it. The halting problem where the input is a positive integer that identifies a Turing machine, is undecidable. The variant halting problem where the input is a positive integer that fits in 64-bits is decidable and can be implemented in $O(1)$ runtime; but this is a useless result that doesn't help anyone! (because the mapping table that would decide it is impractically vast, even though technically finite, and actually figuring out all the entries that should go in the table is probably impossible in the real world)

So basically, the standard tools of this sort of computer science theory just aren't useful to analyse algorithms where the input can only be a primitive machine integer. They don't usefully divide problems & algorithms into different classes unless we are considering problems that have an infinite space of inputs that can be of unbounded size. And primitive numeric types as implemented in actual CPUs and programming language don't meet this criteria. It is fundamentally impossible to do constant-time comparisons and basic arithmetic on numbers of unbounded size, CPUs can only do it because they work with bounded numbers.

For example, taking a number $n$ and printing the numbers from $1$ to $n$ is not $O(n)$ if we're being fully general. Simply incrementing a number that is of unbounded size (and might require many many more than 64 bits to represent) in the worst case requires us to traverse all of the digits. Even if we assume each 64-bit chunk of bits can be handled all at once in a single operation, the number of 64-bit chunks is linear in the representation size of $n$ (which is logarithmic in $n$ itself). But if we constrain our program to only take an $n$ that can fit in a single 64-bit word, then the worst case runtime is $O(2^{64})$ which is also $O(1)$ since constant factors aren't relevant to big-oh analysis.

For a real algorithm that takes a number as input to match up with the this kind of theoretical analysis, the input needs to be not a primitive type like a 64-bit integer, but rather an arbitrary size (and/or precision) number; a lot of languages have "bignum" types and libraries that support this. These effectively use primitive machine types as digits in a base $2^{64}$ (or whatever) number system; numbers are variable length sequences of symbols rather than single symbols, and operations like arithmetic and comparisons take time proportional to the number of "digits" rather than being constant time.

Most of the time real programs simply don't need to ever be given inputs large enough to require arbitrary-precision numbers. For example your "print every number from $1$ to $n$" program is already getting up to the scale of the age of the universe to run just with the largest possible 64-bit numbers (depending on exactly how many we can print a second). So programmers take the shortcut of just assuming they'll only ever need a number that is a single "digit". That shortcut makes lots of algorithms much "faster" than we would get from analysing them as if they were Turing machines reading numbers encoded in an unbounded number of symbols, but technically this is only because they don't actually solve the infinite problem such a Turing machine would solve, only the finite number of cases that we care about in practice.

If we're being very pedantic this issue applies with almost all programs, not just ones involving numbers. Real programs run on an actual machine always have a finite bound on the amount of memory they can use, which stops them from actually being able to solve problems of arbitrary size, and thus technically makes their "real" complexity degenerate. But analysing a string-processing algorithm as-if the strings could be unbounded still produces useful knowledge because programmers are simply used to thinking about strings as variable-sized with operations on them taking time dependent on the size of the string. The point where the big-oh bound takes over and dominates any lower-order term (that can be larger for small inputs) tends to in practice occur at small enough magnitudes that it's still well within the scale of inputs that actually occur, and so it produces useful results to take the classifications we get from analysing idealised infinite-capacity algorithms and applying them to algorithms that will run on real machines implemented in real programming languages.

But if you're processing numbers and only accepting numbers with a finite bound, you need to do a different analysis with different assumptions than standard basic complexity analysis. Giving your runtime bound in terms of the magnitude of the input rather than the size of its representation and assuming basic operations are constant time can produce quite reasonable results for a working programmer; they would be technically wrong as general statements for infinite problems requiring unbounded input, but if that's not what you actually want to analyse it doesn't necessarily matter much.

---

¹ If we're being properly rigorous we really should, as Caleb's answer points out, explicitly consider and state what variable we're actually using in the expression we're using to bound the input. It doesn't have to be the size of the input but that's usually the "default", especially in informal discussions like those that tend to be made by programmers rather than academics.

There's also some subtleties in what quantity is actually being bounded by the big-oh expression too. For example most programmers with any exposure to complexity theory have heard of the idea that an optimal comparison-based sorting algorithm has time complexity $O(n \cdot \log n)$. But what is often missed is that this bound is abstracting over the actual size of the items being sorted and the time it takes to compare them. This is not a bound on the total number of operations in running the sorting algorithm. $n$ in this expression is the number of items to be sorted, and the quantity being bounded is the number of comparisions that will be needed (regardless of the number of operations it takes to compare two items).