patternMajor
Measuring time complexity in the length of the input v/s in the magnitude of the input
Viewed 0 times
thelengthtimeinputmeasuringmagnitudecomplexity
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#159696, answer score: 20
Revisions (0)
No revisions yet.