Why don't we consider them as linear? I don't understand. You just have to check for factorization up to sqrt of n. So it's even faster than linear. I assume it's not linear only if we compare the number of operations relative to the input in terms of binary representation. But why would we do so? It seems to me wrong. The growth in calculation should be calculated compared to the number itself. Why do we compare it to the binary representation?
$\begingroup$
$\endgroup$
16
-
$\begingroup$ You're assuming that a single divisibility check is a constant-time operation, which is definitely not true if you let the numbers get arbitrarily large. In fact it's more than O(n). $\endgroup$– hobbsDec 28, 2018 at 2:38
-
$\begingroup$ So this is the answer. Not that we care about the binaric representation . You are basically giving a different reasoning is that correct? $\endgroup$– bilanushDec 28, 2018 at 2:44
-
1$\begingroup$ No, just pointing out an additional problem. $\endgroup$– hobbsDec 28, 2018 at 2:47
-
$\begingroup$ Ok,. It doesn't even say that it takes more than linear for testing devisability only for division itself. $\endgroup$– bilanushDec 28, 2018 at 2:48
-
3$\begingroup$ @bilanush, sorry if I appear straightforward, but you seem insisting one perspective while rejecting others. Please note that even if you have a solid perspective, other different or even competing perspectives can be solid as well. The discussion between you and other looks like some debate contest where you (pretend to?) emphasize your point of view that you just care the numeric value instead of the bit or decimal length of the input number, which is, by all means, just your choice and not wrong. But the other side is likely to have an equal footing as you. Possibly ten times better. $\endgroup$– John L.Dec 28, 2018 at 6:05
|
Show 11 more comments
4 Answers
$\begingroup$
$\endgroup$
8
It seems that the main sticking point of the question here is: Why express runtime in terms of the size of the input, rather than the numeric value that the input represents? And indeed in some cases it doesn't make much difference which way you choose to express it. For instance, we could say that the time to read all values in an $N\times N$ matrix is quadratic in the number of columns, or we could say it is linear in the number of cells, and the meaning of these is the same, just with different conventions.
So let's look at some reasons why it is conventional to express operations on numbers in terms of the length of the number rather than its numeric value:
It is more easily comparable to operations on other kinds of data, since every possible form of input has a length but not all forms of input have a numeric value. By consistently using the length of the input as our reference point across a variety of problem types, we also get some nice properties like "the runtime of an algorithm that reads the entire input can never be better than linear."
It provides more useful time complexities in context. For instance, a common use for primality testing is for cryptography. When we're doing cryptography, we might use say a 512-bit number as a key. We would like to have algorithms that scale proportional to the length of the number (512), rather than its numeric value (about $2^{512}$), since $2^{512}$ is such an astronomically large number that even a "linear" time algorithm would never realistically finish.
It relates better to the actual operations performed by the computer. Many people are accustomed to implicitly treating all numbers as capped at some fairly large constant like $2^{64}$, and thus all arithmetic operations are constant-time and the actual internal representation of the number is irrelevant. But when we are analyzing the big-O performance of operations on the number itself we cannot assume that numbers are always small enough to ignore their internal representation. Ultimately, these operations are performed on bits so the number of bits is a good reference point to use for describing the performance.
As a thought experiment, try analyzing the performance of the addition operation. You may have always considered it a constant-time operation, but what happens if the numbers in question get arbitrarily large? Ultimately, you'll need to sum each digit one-by-one, carrying as necessary. It makes sense to describe this as a linear-time operation based on the length of the input, rather than logarithmic time based on the numeric value of the input.
-
$\begingroup$ Thank you. It seems as if there is something I am missing. Since I don't really get the logic for reffering to the size of input at all. As to your reasoning, please note, that I am too calculating the number of operations that performed on the input size. This we are doing the same. The only difference is, that I want to compare it to the magnitude of the number because this is what we are dealing with. We are asking about 'primes' meaning about the magnitude of the numbers themselves. Reffering to the size of input is a bit deceving since what we care about are the numbers. $\endgroup$– bilanushDec 28, 2018 at 19:26
-
$\begingroup$ Basically, what's the point of asking how complex the code become as we are adding another zero to the end of input? What we really care is how difficult the code gets as I move even just from 100, to 101 to 102 ... So on. And this doesn't get into account here in your way of calculating. More so, you are getting different result. In my way it's sublinear and you are getting a far worse complexity which isn't true. $\endgroup$– bilanushDec 28, 2018 at 19:32
-
$\begingroup$ Because if I ask how worse do I get when I do a prime test on 10 compared to 100 the real answer is that it's linear or even sublinear sqrt( 2^7/2^4). There is something I am really missing here. $\endgroup$– bilanushDec 28, 2018 at 19:32
-
$\begingroup$ It's just a convention that happens to be convenient, that is all. It's not a matter of true or false, just different ways of writing the same thing, like using base 10 vs. base 2. Describing it in terms of the numeric value is fine, in fact some sources do so. But just keep in mind that there are in fact exponentially faster primality testing algorithms than the one you described above (see the linked page), and for primes of the sort used in cryptography (512+ bits) your "sublinear" algorithm will be too slow. $\endgroup$ Dec 29, 2018 at 0:02
-
$\begingroup$ Thanks. What I understand by now is, that we really don't care because there's a one to one corresponding. This looks fine to me. The only thing that's still annoying me , is when reffering to this as an inefficient algorithm. This looks to me wrong. Because still in terms of the the real prime number it's still sub linear. So why do we choose to look at the size of the input and then say it's inefficient. (What you say that there are faster ways , I know it. I am purposely talking about this algorithm which check each number for divisibility) $\endgroup$– bilanushDec 29, 2018 at 15:53
$\begingroup$
$\endgroup$
9
Simple. When you give the number one trillion as input to your algorithm, do you give it as 1'000'000'000'000, or as a terabyte large string of ones?
And by all means, you are free to choose whichever representation you feel comfortable with.
We analyze the runtime as a function of the size of the input, not as the magnitude of the number represented by the input were the input to be a number.
-
$\begingroup$ Sorry. But this is exactly what I don't understand. Why do we care about the binary representation ? It just looks like a manipulation of looking at it's binaric input and asking about the complexity of it. Why don't you look at the number itself which is what we truly care about. The whole point of complexity is to assess how fast the time grows as we move to greater numbers. So the most logical way of looking at it is by assessing how fast for example grow when we move from 10 to 100 . So it's 2^4 compared to 2^7 the growth is exactly linearly proportional to the input number $\endgroup$– bilanushDec 28, 2018 at 2:18
-
$\begingroup$ We as humans deal with the number itself. Not with it's binaric shape. Why on Earth would it matter the complexity compared to binaric input? We are only trying to figure out how complicated the algorithm gets as we go to greater numbers. It doesn't matter at all the way computer choose to write it. Buttom line we should care only about the number of operations the computer does, and as well as the input. But of course, we should care about the magnitude of the number because this is what we are having in our heads , what is the rate in which the complexity grows as we go to great number $\endgroup$– bilanushDec 28, 2018 at 2:27
-
6$\begingroup$ @bilanush no, we as humans are incapable of doing math on "the number itself". Usually we use the base-10 representation. Which is the same size as the base-2 representation, within a constant factor. $\endgroup$– hobbsDec 28, 2018 at 2:34
-
$\begingroup$ I agree. But think about it. Why should we care about the size of the input????? This is a very cosmetic factor here. What we really care about is how fast the complexity grows as we bring great numbers. What's the point of the need size of input? This tells me nothing. When I am talking about primes what I really care about is the rate of change of going from 1000 to 100000. I really do care about the magnitude of the number. Why should I care about the binaric input? Or even the base 10 representation for that matter. $\endgroup$– bilanushDec 28, 2018 at 2:39
-
$\begingroup$ In complexity we are always talking about the magnitude of the number. Which is what we are dealing with. We are always interested in knowing how complex would it become as I move to greater numbers . $\endgroup$– bilanushDec 28, 2018 at 2:42
$\begingroup$
$\endgroup$
There are two sensible ways to define a variable that can be used in the runtime complexity.
- $m$ is the value of the input number (your definition).
- $n$ is the number of bits required to represent the input (the input size).
Neither is better than the other, because there's a 1-to-1 correspondence between the two:
- $n = O(\log m)$, or equivalently
- $m = O(2^{n})$
Most scientists use $n$. Using that definition, sorting is e.g. $O(n \log n)$ and there's no known $O(n)$ algorithm for primality. You showed that there is a $O(\sqrt m)$ algorithm (sublinear in $m$), which is $O(\sqrt 2^n)$ (exponential in $n$).
Using the definition of $m$, we're not looking for a (sub)linear algorithm for primality; we're looking for a polylogarithmic algorithm, $O((\log m)^c)$ for some constant $c$.
$\begingroup$
$\endgroup$
7
I just got a couple of students curious on this confusion and I tried answering it as follows. (Different to above responses).
First, note that if we were not concerned about the magnitude of input value but only its n-bit representation then the same would apply to analysing sorting algorithms too. But irrespective of what the input numbers magnitude or bits are sorting is nlgn. Agreed?
So why bother on n-bit when dealing with primality or GCD?
To me (and I can be wrong) this is done so to have a worst case complexity analysis. Notice that this part is where my response is different from above.
So going back to sorting, when we say to analyse an input array of size 10^6 we see different cases. And give our big-oh analysis for the worst case of size 10^6. Stay with me!
If we were to plot the nlgn time complexity on x-y what we will do is that we will take an array of size 1, 2, 3,..., 100, 101,..., 1000, ..., 10^5.... and for each of them find the number of basic operation count.
The size of array goes on x-axis and count of basic operation on y-axis. Right? We don't do that too often but that's how we would do it. This would give us an increasing function. I hope you are still reading.
So now back to primality testing. If I plot the same x-y time complexity function and take magnitude on x-axis and count of steps on y-axis, can you imagine what will happen? (Raise of hands, how many of you have guessed the next part?)
For above plot we get following values:
x | y
2 | 1
3 | 2
4 | 1
5 | 4
...
1000 | 2 (why? its divisible by 2)
So we get a zig-zag shape like efficiency function. That's not right, order of growth were supposed to be monotonically increasing, I mean, they should GROW not SHRINK.
So what's actually needed in this case is that we take the number of digits of number of bits of input as the size of input. Now our analysis is meaningful like the sorting example. Why?
It's because for every n-bit (or n-digit) number we take the worst case from the variety of cases. What we can say is that any even number of size n is a best case for primality and any prime number of size n is its worst case.
So we plot the time complexity as a function of bits of the input and not its magnitude.
-
$\begingroup$ I can't really tell what you're trying to say here. It would help if, for a start, you edited out all the chatty comments ("Stay with me!", "I hope you are still reading", "Raise of hands, how many of you have guessed the next part?", etc.) and focused on giving a clear description of your thoughts. I don't see how the "zig zag" function is a problem: you could always obtain an increasing function by looking at "max number of steps for any $m\leq n$" instead of "number of steps for $n$", and you could still bound the running time by giving a "nice" function $f$ such that... $\endgroup$ Feb 20, 2019 at 17:20
-
$\begingroup$ ... the number of steps required to determine if $n$ is prime is $O(f(n))$. Indeed, the question suggests $\sqrt{n}$ as an example of a nice function with this property. $\endgroup$ Feb 20, 2019 at 17:21
-
$\begingroup$ Apologies for the chatty comments. I was just writing the text for some students and pasted here since I landed on this post while googling. $\endgroup$ Feb 20, 2019 at 17:40
-
1$\begingroup$ You can certainly upper bound the number of steps by an increasing function, even though that bound will be very loose for even inputs. And, so what? We don't insist on measuring resources with increasing functions. We normally use increasing functions, and complexity classes are generally defined in terms of them, but that's mostly because it's too hard to compute the exact resource requirements, so we give a bound that's easier to compute. The actual resource usage isn't necessarily increasing, as this example shows. $\endgroup$ Feb 20, 2019 at 18:02
-
1$\begingroup$ Yes. For example, consider your favourite problem on graphs, with an adjacency matrix as input. We don't normally consider things at this level of detail but any graph algorithm on a Turing machine really needs to start by checking that the input is a valid adjacency matrix so, for example, it will reject as soon as it notices that the length of the input is not a perfect square. This gives exactly an oscillating function: inputs of length 2, 3, 5, 6, 7, 8, 10, ... are all rejected in linear time; inputs of length 1, 4, 9, 16, ... might take much longer. $\endgroup$ Feb 20, 2019 at 18:31