Talk:Time complexity/Archive 1

Archive 1

HTML log-star

User:Cybercobra seems to dislike "O(log^* n)", and I think that "$O(\log ^{*}n)\,$" looks totally out of place in the table. Could we perhaps find a HTML version that would be acceptable to everyone? Some attempts (see the source code for details):

O(log^* n), O(log^∗ n), O(log^∗ n), O(log^⁎ n),

O(log^* n), O(log^∗ n), O(log^∗ n), O(log^⁎ n)

The same thing in a larger font so that the differences are easier to see:

O(log^* n), O(log^∗ n), O(log^∗ n), O(log^⁎ n),

O(log^* n), O(log^∗ n), O(log^∗ n), O(log^⁎ n)

Any comments? (Personally, I think the 8th version looks best, but the 3rd one might be a reasonable compromise, as it uses only HTML 4.0 entities and hence should render correctly everywhere.) — Miym (talk) 08:46, 13 January 2010 (UTC)

Only the first one renders on IE6/XP (probably the most common browser/OS combination). Only the first 3 work in Chrome/XP. The 4th and 8th one don't render on Firefox/XP or Opera/XP. I would recommend sticking with the first one for the benefit of poor IE6 users everywhere. If this is fixed in IE7, and we don't care about IE6 users, I vote for the third one. --Robin (talk) 14:24, 13 January 2010 (UTC)

Thanks for the feedback! Another possibility might be a trick like this, using only ASCII characters, but slightly raising "*":

O(log* n), O(log* n), O(log* n)

This seems to look better than a straightforward use of a "sup" element (which raises "*" too much). I created an experimental template {{log-star}}, which we could use like this:

log* function, O(log* n), O(n log* n), ...

— Miym (talk) 15:21, 13 January 2010 (UTC)

And just a minor clarification: The complication here is that in some fonts "log*" looks a bit like $\log *\,$, while in some fonts it looks a bit like $\log ^{*}\,$, and in some other fonts it is a compromise between the two extremes. Therefore a superscript-* looks strange with some fonts, and a non-superscript-* looks strange with some fonts. That's why I would suggest a "slightly raised *" as a compromise that might be tolerable in all situations. — Miym (talk) 15:30, 13 January 2010 (UTC)

How about just using $\scriptstyle O(\log ^{*}n)$? --Robin (talk) 14:56, 15 January 2010 (UTC)

This would also look out of place since it's still a LaTeX picture. On the other hand, wikipedia's LaTeX pictures always look out of place and that is an issue which should be addressed in general. For now, I think the template is a good solution. ylloh (talk) 18:16, 15 January 2010 (UTC)

I like the latest version using {{log-star}}; nice work Miym. --Cybercobra (talk) 20:30, 15 January 2010 (UTC)

Sub-linear time algorithms

User:Eldar added: [1]

The specific term sub-linear time algorithm is usually reserved to algorithms that are run over fresh inputs with no assumptions on the input structure (unlike binary search or tree maintenance algorithms), and use neither parallel processing (as the NC₁ matrix determinant calculation does) nor non-classical machines (as Grover's algorithm does)

I don't agree that sub-linear time algorithms exclude all other models of computation. Just like polynomial time makes sense for sequential machines, parallel machines, quantum computers etc., I think sub-linear time should make sense for all models too. Perhaps the prevailing use of sub-linear time algorithms is related to property testing, but that doesn't mean that Grover's algorithm isn't a sub-linear time algorithm. It is sub-linear time on a different model of computation. --Robin (talk) 01:52, 15 January 2010 (UTC)

Yes, I also think that the term "sub-linear time algorithm" makes sense in any model of computation. As another example, in distributed computing, it makes perfect sense to say that an algorithm runs in sublinear time (= number of communication rounds is o(n), where n is the number of nodes in the network). Hence I would suggest that we first define what sub-linear time means in general (and perhaps point out that constant time or logarithmic time is sublinear time), and then explain the properties of sub-linear time algorithms in some models of computation (e.g., emphasise that if there is no parallelism, then a classical machine can't read the entire input, and point out that Turing machines don't make much sense in the study of sub-linear time algorithms). — Miym (talk) 09:39, 15 January 2010 (UTC)

The intention was not to make claims on how the term should be used, but on how this specific phrase is actually used in the community. If you see "sub-linear algorithm" in a research paper, this is what the phrase will almost always refer to, regardless of whether this is right.Eldar (talk) 22:36, 15 January 2010 (UTC)

I agree that it is commonly used in that sense, but I don't think you can say "almost always". A quick experiment with Google Scholar, "sublinear time": hit #4: deterministic parallel algorithm; hit #5: distributed algorithm; hit #7: sublinear-time updates in dynamic data structures. There are reasonably many hits for phrases such as "sublinear parallel algorithm". It is even used in standard textbooks in the broader sense: e.g., CLRS seems to use the phrase "sublinear time" in the context of sorting networks (Section 27). What it means in the community may depend on which community you consider. :) — Miym (talk) 23:21, 15 January 2010 (UTC)

The specific use is for the three-word phrase "sublinear time algorithm" (usually without a hyphen in "sublinear"), and indeed that section was a merged stub article dealing with those. I'm starting to wonder whether things would be served better by unmerging. Eldar (talk) 22:44, 16 January 2010 (UTC)

I tried reconciling the issues raised here within the section. Take a look. Eldar (talk) 01:15, 21 January 2010 (UTC)

Thanks, in general, I think it looks fairly good now. The last paragraph might require some editing, though:

• The 3rd paragraph says that sublinear-time algorithms "must be" randomized, and the last paragraph says that the are "typically" randomized.
• The reference to streaming algorithms may be a bit confusing (exactly what is sublinear in what; streaming algorithms by definition read all bits of input).

— Miym (talk) 09:11, 21 January 2010 (UTC)

I took care of the above. First bullet: one could nitpick that there are cases in which randomization is not required (e.g. for checking trivial "properties") so I changes the first reference to randomization. Second bullet: Indeed "streaming" was inappropriate and now removed. Eldar (talk) 00:57, 22 January 2010 (UTC)

SUBEPT and fixed parameter tractability

User:Ylloh recently added the following text to the article:

Note that it makes a difference whether the algorithm is allowed to be sub-exponential in the size of the instance, the number of vertices, or the number of edges. In parameterized complexity, this difference is made explicit by considering pairs $(L,k)$ of decision problems and parameters $k$. SUBEPT is the class of all parameterized problems that run in time sub-exponential in k and polynomial in the input size n:

${\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right)$.

More precisely, SUBEPT is the class of all parameterized problems $(L,k)$ for which there is a computable function $f:\mathbb {N} \to \mathbb {N}$ with $f\in o(k)$ and an algorithm that decides $L$ in time $2^{f(k)}\cdot {\text{poly}}(n)$.

While I find fixed parameter tractability very interesting, I don't think it should be mentioned in this article. We don't mention the class FPT, which is arguably the most important class in parametrized complexity theory. I think this article should continue to be about time complexity in one variable n, and not the type studied in parametrized complexity --- I think that would confuse the reader too. --Robin (talk) 14:01, 8 March 2010 (UTC)

References

First of all, let me mention that I would not want to define the term sub-exponential in a wikipedia entry twice, with two different meanings. This may be very confusing for a reader unfamiliar with the subject matter and it is why I changed the headings from "First Definition" to "SUBEXP" earlier. On the other hand, wikipedia should only mirror the actual uses of that term and unfortunately these two formalizations are indeed used. So I did not object when you reverted the headings.

I partially disagree with your remark above. Defining the term sub-exponential as $2^{o(n)}$ with n being the input size may look like a robust notion, but it isn't. Just notice that we have no idea whether ETH can be formulated in terms of the size alone, without using the number of variables or clauses of a formula (a 3CNF formula with m clauses may be of size $O(m\log m)$). The sparsification lemma does not give us formulas of linear size, it only gives us formulas with a linear number of clauses. Of course, when we talk about running times of $2^{\sqrt {n}}$ for natural problems then logarithmic factors for encodings make no difference -- both are $2^{o(n)}$. However, at the current state of research and from a complexity theoretic perspective, we need a parameter different from the input size to formally talk about sub-exponential time in the sense of the second definition. ylloh (talk) 15:18, 8 March 2010 (UTC)

Order of sections

I rearranged the linear and polynomial sections to be more in line with the standard presentation, but then realized that the sections seemed to go in order. For the table, that makes sense, but I'm not sure it makes the most sense for the article sections, so I've left it going constant, linear, polynomial. I won't be offended if someone else disagrees and reverts, but I figured I'd explain my reasoning. jhe_iv (talk) 22:37, 25 May 2010 (UTC)

Typos

In the subsection "Exponential time hypothesis" the symbols m and n seem to refer to the same thing. —Preceding unsigned comment added by 193.219.42.53 (talk) 10:54, 18 June 2010 (UTC)

Comment on text

Not sure how to add comments on text, but as I'm not sure what change to make on the page I'll describe what I mean here. In the section "Constant time" the following can be read "Hence it is a linear time operation, taking O(n) time (unless some more efficient algorithm is devised, for example, a binary search across a sorted array)". The algorithm referred to is an algorithm to locate the minimum value in an array. My question regards the paranthesis; why would a binary search be needed across a sorted array to obtain the minimum value? We could just index the first (or last) element in the array, and we would have the minimum. What am I missing?

85.24.185.204 (talk) 12:12, 12 December 2010 (UTC)

Subexponential-time algorithms for NP-complete problems

The section "Quasi-polynomial time" > "Relation to NP-complete problems" asserts "All the best-known algorithms for NP-complete problems like 3SAT etc. take exponential time", which could easily be interpreted to contradict the NP-complete page section "Common misconceptions" where it is asserted: "Further, some NP-complete problems actually have algorithms running in superpolynomial, but subexponential time." This issue was raised but not resolved on the latter page's talk page under topic "28 Exponential time as a misconception?". Grammatically, "best-known" would mean those algorithms most well known, but this usage is easily confused with "best known", meaning the algorithms with best performance known, and I suspect the latter was the intended meaning. Can anyone comment on the meaning and correctness of this statement? Thomas (talk) 06:10, 9 January 2012 (UTC)

KD-Tree search timing mismatch

Hi, on Kd-tree it says that searching is O(log(n)). Here it iays that it is n^c , 0<c <1 129.67.86.189 (talk) 19:55, 23 March 2012 (UTC)

n is not clearly defined

To someone who is not familiar with the subject, equating n with "size" is unclear. It would be helpful to have an explicit definition along the lines of "n is the size of the input measured in bits," or "n is the size of the input measured by its length as a string of characters in a given finite alphabet". At least something to the effect that n(ABCD) = 2^32 bits in ascii, or n(ABCD) = 4 characters, rather than say, n(ABCD) = 65666768 by converting the ascii to a decimal number. This can be a potential source of confusion, because O(exp(n)) often describes the number of steps in a naive algorithm, so it is not clear that this is not the desired definition of size. — Preceding unsigned comment added by 168.122.117.36 (talk) 18:32, 5 July 2012 (UTC)

Strongly and weakly polynomial time

There is this sentence in the second-last paragraph:

"There are algorithms which run in polynomial time in the arithmetic model (where arithmetic operations take constant time), but not in the Turing machine model. The Euclidean algorithm [...] is one example."

This seems wrong to me. The constant-time operations in the arithmetic model become polynomial-time on a Turing machine, so polynomial-time stays polynomial-time. This is fine for showing an algorithm that is not strongly-polynomial (in either TM or AM), but that is not what the sentence says. — Preceding unsigned comment added by 129.132.58.129 (talk) 09:55, 9 October 2012 (UTC)

I checked out the cited source (Grotschel 1988) at the library, and corrected the article accordingly. The source states verbatim: "For instance, the well-known Euclidean algorithm to compute the greatest common divisor of two integers runs in polynomial time in the Turing machine model but not in the arithmetic model." The Wiki had the Euclid's GCD exemplifying the opposite. I also made the statements about "running time" more specific, since "steps" and "length of input" are defined differently for the two models. Note that some of the statements made by 129.132.58.129 above might be a bit misleading (e.g. it doesn't make sense to talk about strongly-polynomial "in a model"). See this answer for the details (as I see them, at least).

Alexeicolin (talk) 00:45, 22 December 2012 (UTC)

Ask for clarification

From section "Sub-linear time", what is a string that has a 1-bit indexed by the first log(n) bits? --151.75.122.18 (talk) 20:19, 14 March 2014 (UTC)

Exponential time is on the table twice?

Why is exponential on the table twice? And both above and below factorial time.

2^O(n) is asymptotically slower than n! The Big-O tells us that 2 raised to any constant times n will not grow faster than n! However, poly(n) is polynomial in n. n^5 or n^20 is polynomial in n. 2^(n^5) will grow faster than n! As a simple rule to follow, 2^(cn) = O(n!) where c is some constant. n! = O(2^(n^k)) where k > 1. Krohn211 (talk) 19:13, 5 October 2014 (UTC)

Importance of average-case complexity

Regarding this revert by Eldar: why shouldn't average-case complexity be mentioned in the lede? Even if "average case is not as common as worst case", it is important for understanding many common algorithms, including quicksort, quickselect, simplex, BST operations and hash table operations. QVVERTYVS (hm?) 23:22, 3 January 2015 (UTC)

When "Time complexity" is used without stating average/worst case, it means worst case. I must admit that while the textbook version of quicksort (random choice of pivot) has a guarantee for the worst case, the usual implementations do not. I'll do some corrections now. Eldar (talk) 05:08, 4 January 2015 (UTC)

Strongly polynomial requires integer inputs?

Time_complexity#Strongly_and_weakly_polynomial_time says, a polynomial in the number of integers in the input instance. Why is it important that the inputs be integers? Obviously, you can make a slight generalization and talk about any inputs which can be mapped to integers (i.e. you can represent a string as a very long integer, or a fixed-point rational number can be scaled to be an integer), but why need non-integer inputs be excluded? -- RoySmith (talk) 13:03, 10 September 2010 (UTC)

Really, "weakly polynomial" is just a synonym for "exponential" for positive inputs. It gets a special name only because we think about numbers differently; I don't see the same reason applying to non-integer inputs. CRGreathouse (t | c) 14:38, 10 September 2010 (UTC)

The article implies that "weakly polynomial" is a synonym for "polynomial," not for "exponential," which makes sense. The "synonym" to "exponential" that you might be thinking of is "pseudo-polynomial," which is in fact exponential on log-encoded input if it is polynomial on an unary-encoded input. Another reason to list the definitions all in one list together.

Alexeicolin (talk) 04:16, 18 December 2012 (UTC)

I agree with RoySmith, the definitions for strongly/poly/pseudo could be combined and stated simply, without invoking arithmetic model, space, and strage notion of "number of integers in the input instance", like so, in order:

Definition 1 An algorithm runs in strongly polynomial time if the number of operations (basic

arithmetic operations, comparisons, etc.) can be bounded by a polynomial in the number of data

items, and it is not dependent on the size of the data items.

Definition 2 An algorithm runs in polynomial time if the number of operations can be bounded by

a polynomial in the size of the input, when data items are encoded in binary.

Definition 3 An algorithm runs in pseudo polynomial time if the number of operations can

be bounded by a polynomial in the size of the input, when data items are encoded in unary.

Source (re-ordered): ORIE 633 Lecture Notes, David P. Williamson, Cornell University

Alexeicolin (talk) 04:16, 18 December 2012 (UTC)

I agree with RoySmith as well, Alexeicolin, and with you, too. Are you still there? I strongly encourage you to be bold and go ahead, if you're still there of course, and make the changes you have in mind. There is absolutely no need, in particular, to limit the subject to integers–complexity theory indeed applies to numbers of data items in general, not just numbers of integers: that is in fact a part of the beauty of it–and imo it is a disservice to the reader to suggest otherwise.

I really hope you're still there; getting something done on Wikipedia, when you actually try to cooperate with people, appears dismayingly similar to breeding elephants (i.e. is only accomplished at high levels, involves a lot of yelling & screaming, and takes two years to get results).--IfYouDoIfYouDon't (talk) 01:39, 8 April 2015 (UTC)

GraphIsomorphism example

Section 12.2 (second definition of subexponential time) lists the best known algorithm for the graph isomorphism (GI) problem as an example. If I am not mistaken, then with Babai's new result (http://arxiv.org/abs/1512.03547) on GI this example is now wrong.

--131.130.117.228 (talk) 13:19, 11 January 2016 (UTC)

Logarithmic time

In the introductory paragraph to this section the claim is made that "Due to the use of the binary numeral system by computers, the logarithm is frequently base 2 (that is, log2 n, sometimes written lg n)" I don't think this is true but that the actual reason is the fact that most algorithms that have a logarithmic time complexity component involve a splitting operation, such as binary search or binary trees. Another obvious reason for preferring log base 2 is that it is the simplest meaningful log base. Computers using a binary numeral system and discussions of logarithmic time defaulting to log base 2 seem to both be the result of a similar cause rather than the former being the cause of the latter. — Preceding unsigned comment added by 2620:0:1002:0:4814:C258:2C23:3187 (talk) 00:35, 24 May 2016 (UTC)

Quasilinear complexity

This section of the article contained the sentence

Quasilinear time algorithms are also O(n^1+ε) for every constant ε > 0, and thus run faster than any polynomial in n with exponent greater than 1 by a positive constant.

The second part of this sentence is a nonsense, because an algorithm cannot run faster than a polynomial and "greater than 1 by a positive constant" does not means anything.

I have tried to fix these nonsenses, and I have been reverted twice. In my first edit, I have simply removed the part of the sentence beginning with "thus", because it is nothing else than a bad explanation, in words, of the formula of the first part. I have been reverted with the edit summary "it is blatantly false that all algorithms have integer exponents and that non-integer exponents are excluded from polynomial time", which does not refer to my edit but to my edit summary, in which I noted that the exponent of a polynomial is necessarily an integer.

As an explanation of the formula seems necessary for some editors, in my second tentative, I have rewritten the second part of the sentence into ... and thus run faster than any polynomial time algorithm that has an exponent greater than 1. This has been reverted with the edit summary your version is incorrect. QP is not better than n^{1+(loglog n)/2) despite loglogn/2 > 0 but it is better than n^{1.1}). This asserts implicitly that the exponent of a polynomial time algorithm may be not constant. I have never seen any source considering non-constant exponents for polynomial time, and the section "Polynomial time" asserts that the exponent is constant. Nevertheless, in a third tentative I have replaced "exponent greater than 1" by "constant exponent greater than 1". I hope that the editors who are not satisfied by my edits will improve it instead of restoring nonsenses.

By the way, two more remarks:

1. Section "Polynomial time" does not defines the exponent of a polynomial time algorithm. The disputed sentence, in all its versions use "exponent" for "least exponent"; in fact a quasilinear time (and even a linear time) is a polynomial time which has any number greater than 1 as an exponent. Thus the second part of the sentence, in all its versions, means that a quasilinear time algorithm run faster that a linear time algorithm.
2. For being correct "run faster" should be replaced by "run faster for n large enough" or "run asymptotically faster".

D.Lazard (talk) 08:47, 27 September 2017 (UTC)

It is important to note that "polynomial" here does not mean a polynomial in the mathematical sense; it is short for "polynomially bounded time complexity" which could include complexities like $O(\exp({\sqrt {\log n}}))$ etc. So what is intended here is that quasilinear is faster than the polynomials $O(n^{1.1})$, $O(n^{1.01})$, $O(n^{1.001})$, etc., whose exponents are greater than one by positive constants 0.1, 0.01, 0.001, etc. However, quasilinear is *not* faster than the time bounds (which are still polynomial time bounds) $O(n^{1+0.5\log _{n}\log n})$, $O(n^{1+0.4\log _{n}\log n})$, $O(n^{1+0.3\log _{n}\log n})$, etc., all of which are still polynomial time (just as $O(n\log n)=O(n^{1+\log _{n}\log n})$ is polynomial time) and are written with exponents > 1 but by amounts $0.5\log \log n$ that are more slowly growing than constants. The text you keep reverting says all this. Your version does not; an earlier version incorrectly implies that quasilinear is faster than all of those time bounds and the new version only applies to certain very special time bounds, the ones of the form n^c for constant c.

Another way of saying the same thing: we can define the "exponent" of any time bound $T(n)$ to be $\log _{n}T(n)$. We want to consider the property that this exponent is bounded away from 1, not merely that it is greater than one (in both cases for all sufficiently large $n$). Can you think of a way of rephrasing the sentence in question that expresses this property correctly (yours doesn't) and that doesn't get bogged down in technical definitions (as the way I have just expressed it does)? —David Eppstein (talk) 11:43, 27 September 2017 (UTC)

I know enough of complexity theory for understanding what it was meant. However Wikipedia is not written for people who are accustomed with any jargon (here jargon of complexity theory). Thus an abbreviation such as "polynomial" for "polynomially bounded time complexity" must not be used without being defined or linked, especially when it may induce a confusion for a non-specialist. The same for "greater than one by a positive constant" instead of "greater than one by a positive constant factor", which is not the same as "greater than one by a positive constant addend".

The accuracy of the formulation is specially important in articles about complexity, because of the many errors that non-specialists can make when talking of complexity. I remember a referee report by a very good mathematician, which contained several such errors. The article was about an algorithm that allowed to solve in a few minutes several challenging problems that were not accessible with previous software. The report was in substance "One know since more than 20 years simply exponential algorithms for these problems; the presented algorithms use a tool (Gröbner bases) that has a double exponential complexity; thus there is nothing new". The errors was: 1/ The double exponential complexity is a worst case complexity, and this does not implies that the complexity is exponential for the class of problems addressed by the paper. 2/ The constants occurring in exponents for the simply exponential complexity are so high that nobody has ever tried to implement these simply exponential algorithms. 3/ For the range of problems that are accessible with the present state of technology, the doubly exponential complexity gives a faster algorithm that the simply exponential complexity (asymptotically faster does not imply faster in practice).

More generally the Wikipedia articles about complexity are not written for non-specialists, although everybody who works with algorithms should be concerned by complexity. It results that, when talking of the complexity of an algorithm in a mathematical page, it is very difficult to find the proper wiki link. This is the reason for which I have recently transformed Computational complexity (which was a dab page) into a broad-concept article. It remains to expand it properly for explaining the role played by the model of computation (Türing machine, RAM machines, sequential, parallel, deterministic or not, quantic, ...), the difference between the various resources that are considered (time, space, arithmetical operations, ...), the equivalence between running time and number of steps, the reason of working up to a constant factor, the distinction between worst case and average complexity, ... In fact, it seems that there is no WP article for explaining these concepts for non-specialists and for guiding them among the various technical articles. D.Lazard (talk) 14:05, 27 September 2017 (UTC)

Explain notation before using it

The Θ notation is used straight out of the blue without any explanation or even a reference. — Preceding unsigned comment added by 217.138.46.98 (talk) 17:45, 2 February 2018 (UTC)

I have added a link for the notation. 21:19, 2 February 2018 (UTC)

An expert of this subject is needed ...

... for improving the section Rounding#Rounding_of_summands_preserving_the_total:_VAT_rounding. -- Wegner8 13:05, 30 March 2018 (UTC) — Preceding unsigned comment added by Wegner8 (talk • contribs)

Should be asked at Talk:Rounding, not here. D.Lazard (talk) 14:20, 30 March 2018 (UTC)

Looking again, it appears that the link from Rounding to this article was correct, but that the writing of the section on linear time could be confusing for a non-expert. I have thus edited it for mathematical correction and clarification. D.Lazard (talk) 14:45, 30 March 2018 (UTC)

I do not agree that the Euclidean algorithm uses $O((\log \ a+\log \ b)^{2})$ steps on the Turing machine

Maybe a naive question. I understand that the Euclidean algorithm uses at most $O(\log \ a+\log \ b)$ pseudo-arithmetic operations on numbers with at most $O(\log \ a+\log \ b)$ digits. When implementing the algorithm on a Turing-equivalent machine, we obtain a complexity of $O((\log \ a+\log \ b)^{2})$; this seems to be a bound on the number of bit operations. However, the Turing-equivalence refers to computational capability of mathematical functions. If (since) I can implement the algorithm on my machine, the algorithm can also be executed by a Turing machine. I know that my machine is not exponentially faster than this Turing machine. If my implemented algorithm takes polynomial time $O((\log \ a+\log \ b)^{2})$, then the Turing machine takes polynomial time as well. But does the Turing machine uses exactly the same number $O((\log \ a+\log \ b)^{2})$ of steps with no polynomial overhead? What does "Turing machine steps" mean in the article? Is it moves/steps of the head of a Turing machine on the tape, or bit operations on a "Turing-equivalent" machine like my computer? Daniel.porumbel (talk) 13:15, 19 July 2017 (UTC)

Every step of a Türing machine may be simulated by a fixed number of bit operations on your computer. Conversely, every bit operation that is used in Euclidean algorithm may be simulated on a Türing machine in a fixed number of steps. In other words, for the elementary operations that are involved in Euclidean algorithm, there is a linear equivalence. As far as I know, non-linear equivalence occurs only for operations that require memory modification, and, therefore, cannot be simulated by copying data in a new region of the memory. This is the case of the use of pointers. This is the reason for which Schönhage, in his article "storage modification machines" can obtain a faster algorithm for integer multiplication (O(n log n)) instead of O(n log n log log n)). D.Lazard (talk) 14:37, 19 July 2017 (UTC)

Thank for this quick response. I did not know. Daniel.porumbel (talk) 15:45, 19 July 2017 (UTC)

In fact, after investigating it again, it is not so clear that a Turing machine can take less than $O((\log \ a+\log \ b)^{2})$ for performing an addition $a+b$ ? If you think one can add/subtract two integers $a$ and $b$ in $O(\log \ a+\log \ b)$ on the Turing machine, maybe you could contribute to this CS forum? As it stands, nobody answered this yet with an algorithm of complexity below $O(\log \ a+\log \ b)^{2}$. Daniel.porumbel (talk) 12:43, 20 July 2017 (UTC)

Regarding the integer multiplication, the classical Schönhage-Strassen algorithm takes $O(n\log n\cdot \log \log n)$. The more recent Fürer's algorithm takes $O\left(n\log n\ \cdot 2^{O(\log ^{*}n)}\right)$ where log*n is the iterated logarithm, which is less than $O(n\log n\cdot \log \log n)$. This new complexity seems to be proven on a multi-tape Turing machine, so I suppose the algorithm can not achieve the same complexity on a standard Turing machine. However, I could not find an algorithm that runs in $O(n\log n)$. Maybe Schönhage obtained this in "Storage modification machines" on some other fictitious machine? Daniel.porumbel (talk) 12:43, 20 July 2017 (UTC)

Conclusion

Unless someone comes with a contrary argument that is non-personal and scientifically-rigorous (not the case yet, see responses below), I propose replacing

the running time of the [Euclidean] algorithm is bounded by $O((\log \ a+\log \ b)^{2})$ Turing machine steps.

with

the algorithm performs $O(\log \ a+\log \ b)$ arithmetic operations on numbers with at most $O(\log \ a+\log \ b)$ bits.

This makes the point of the article crystal clear (i.e., the algorithm can not be strongly polynomial although it is polynomial on input size $O(\log \ a+\log \ b)$) and it is less debatable.

As for me, I am far from convinced that the number of 1-tape Turing Machine (TM) steps can be $O((\log \ a+\log \ b)^{2})$, although proving the contrary is not immediate. However, I think it can be shown as follows. The MOD operation on two numbers stored on $O(m)$ bits has as particular case the equality testing on integers on $O(m)$ bits, as well as the difference of two integers on $O(m)$ bits. Comparing/summing/subtracting integers on $O(\log \ a+\log \ b)$ bits requires $O((\log \ a+\log \ b)^{2})$ TM steps, at least with the algorithms I could find. For instance, the currently available algorithms for equality testing are quadratic, because the TM has to do some zigzagging to compare two binary integers/strings [1], see also the ps. Even if the magnitude of the integers decreases, I still see a total of more than $O((\log \ a+\log \ b)^{2})$. If we start from Fibonacci numbers such that the larger one is stored on $m$ bits, at the next iteration we have two Fibonacci numbers such that the larger one is stored on at least $m-1$ bits (check that $F_{i+1}/2<F_{i}$). Summing up $m^{2}+(m-1)^{2}+(m-2)^{2}+\dots +1^{2}$, we obtain a $m^{3}$ term.

ps. A problem related to (binary) integer comparison is integer palindrome which is proved to require quadratic time [2]. I think we can modify any TM algorithm for integer comparison to solve integer palindrome. Assume the TM starts with two integers: one at left of the head, one at right. Each move over the left positions can be mirrored (reflected) over the right positions. We build a mirrored TM: each time the initial TM is at a position $-x<0$, the mirrored TM is at position $x$. If a TM solved integer comparison in linear time, this modified mirrored TM would solve integer palindrome in linear time. Daniel.porumbel (talk) 13:19, 23 July 2017 (UTC)

REFS

1. Turing Machine Example 2, courses.cs.washington.edu/courses/cse431/14sp/scribes/lec3.pdf

2. F.C. Hennie, One-tape off-line turing machine complexity Inform. and Control, 8 (1965), pp. 553-578

If you do not understand the standard time complexity model of one-tape Turing machines, you should not be threatening to edit this article. It is true, and an important example, that the Euclidean algorithm takes a polynomial number of Turing machine steps but not a polynomial number of arithmetic operations, because the polynomials are in different things (numbers of Turing machine tape cells for the input vs number of input values). See e.g. [2] [3] [4] for sources for this claim and its significance. Here "steps" can only mean steps of the Turing machine, not (as you bizarrely suggest) bit operations and not steps of a simulation on some other computational model. I am not certain that the Turing machine time for the Euclidean algorithm should be the square of the input length rather than some other exponent; that should be taken from reliable sources.. If we can't find sources for the specific exponent two, the correct change would be to replace it with "polynomial", not to write something else irrelevant in its place because of your lack of understanding. —David Eppstein (talk) 20:36, 27 July 2017 (UTC)

@ David Eppstein, If you read my conclusion section more carefully, you'll see that I did not even use the word "polynomial". So I fail to see why do you argue on something related to a polynomial number of arithmetic operations. I repeat, my proposal was not to say anything about polynomials but only "the algorithm performs $O(\log \ a+\log \ b)$ arithmetic operations on numbers with at most $O(\log \ a+\log \ b)$ bits." I really do not see how this can be wrong, and it makes the point of the article crystal clear (i.e., the algorithm can not be strongly polynomial), even if I think you'd like to call it irrelevant. Anyway, I'll reduce my argumentation (you are right, this is not reliable source). I only leave a proposal with a proof supporting it and I rest my case. So do not worry, I threaten nothing. You might know more than theory than me so I let you (or anybody else) judge. And this is my last edit, I won't continue such discussion further.

Yes, you do not use the word polynomial. That is the problem. You are proposing to strip out the point (it is polynomial) and replace it by something vague (if you know the time complexity of the operations you might be able to calculate the total complexity of the algorithm) wrong (not all arithmetic operations use the same number of bits) and missing the point (this is about the difference between TM complexity and arithmetic operation complexity, not about the Euclidean algorithm per se). —David Eppstein (talk) 12:15, 28 July 2017 (UTC)

Apparently, you have not understood how the complexity $O((\log a+\log b)^{2})$ is computed. Euclidean division has a complexity of $O(\log(a)\max(1,\log a-\log b).$ Every two steps of Euclidean algorithm reduces the size (in base 2) of the lowest entry by at least one. This implies that the sum over all steps of the $\max(1,\log a-\log b)$ is $O(\log a+\log b),$ giving the complexity of $O((\log a+\log b)^{2})$ for the whole algorithm. If fast multiplication is used, one may reduce the bit complexity to $O(M(n)\log n),$ where $n=\log a+\log b,$ and $M(n)$ is the complexity of the multiplication of two integers of n bits. One does not know if the factor $\log n$ may be removed. D.Lazard (talk) 14:53, 28 July 2017 (UTC)

@D.Lazard, thanks for this well-argued reply. The Euclidean algorithm performs the operation MOD at each step (do you agree on fixing this version?). If the MOD operation takes $O(\log(a)\max(1,\log a-\log b))$, let me apply this Euclidean division algorithm to $a=b$ and the algorithm should answer $0$ in $O(\log(a))$ time. In other words, the algorithm is able to test in linear time the equality of two numbers each one written in $O(\log(a))$ bits (if $a\neq b$, it outputs anything but zero, storing the output on at most $O(\log(a))$ bits--and difference from zero can be checked in linear time). But I think it is not possible to test equality on linear time, based on my argument in ps (equivalence to palindrome). As for me, I did take into account the fact that the numbers become smaller and smaller, but I still can't obtain $O((\log(a)+\log(b))^{2})$. Maybe the above complexity $O(\log(a)\max(1,\log a-\log b))$ is true for a multi-tape TM? Could you please share with me the source of information?

There are two issues here. One is that to get a polynomial number of operations one needs the multiplicative rather than additive form of the Euclidean algorithm (or the binary gcd, a different algorithm) but then the individual operations are not linear time. The other is that this sentence is talking about Turing machine time complexity, not bit operations on a RAM, so things are slower from the overhead of moving the tape from one place to another. It doesn't affect whether things are polynomial vs nonpolynomial but I think it would be safer to take out the exact time bound (unless we can source it) and just say that it's polynomial. —David Eppstein (talk) 16:28, 28 July 2017 (UTC)

@David Eppstein, I still need to reply because with all due respect some of your remarks are really wrong. Check again that saying

"the algorithm performs $O(\log \ a+\log \ b)$ arithmetic

operations on numbers with at most $O(\log \ a+\log \ b)$ bits."

is correct and as non-vague as it could be for a general short sentence on the topic. For me, it is not vague because the polynomiality in input size $\log a+\log b$ is obvious without explicitly saying it, and the non-strongly polynomiality is easy since we only have two integers. Using a plain simple Euclidean algorithm and announcing above is enough to serve the point of the article. If one wants to go into detail, one can see above statement might indeed mean many things like $O(\log \ a+\log \ b)$ (use a word-RAM with $w=\log \ a+\log \ b$), some quasi-linear time like $O((\log \ a+\log \ b)\log(\log \ a+\log \ b))$ using fast integer multiplications on increasingly smaller numbers, or anyway no more than $O(\log \ a+\log \ b)^{3}$ on a 1-tape TM. But distinguishing among such cases is not important, because all cases are anyways examples of polynomial but not strongly polynomial algorithms. If you honestly think about it, your proposal " just say that it's polynomial." is the really vague one, because the reader can not see right away how this something polynomial is not strongly polynomial. And it does not give the slightest clue of how big this polynomial could be (for information only).

You claimed my above statement is wrong, as far as I can see, for an argument like "not all arithmetic operations use the same number of bits". But the algorithm does use only numbers stored on less than $log\ a+\log b$ bits and anything smaller than this does qualify as "at most $\log a+\log b$ bits" as expressed in the statement. This is a simple schoolbook argument, you do not need to be a rocket scientist. Assuming you don't lack some essential knowledge (you might be very confident on this, but it is not so obvious only from your far from in-depth analysis), to see above statement wrong you actually need to want to see it wrong facing any argument whatsoever. I would not be surprised if you dismissed my above reasoning without reading it. I left you a message on your talk page showing you that it is not uncommon to report complexities this way, e.g., the ellipsoid method is reported to require $O(n^{4}L)$ operations on numbers with $L$ digits. I said nothing enlightening in my message to you, but I hope you did learn something from me. As for me, I feel I learned nothing from you.Daniel.porumbel (talk) 22:19, 28 July 2017 (UTC)

Your statement is not wrong, it is strictly weaker than the better known result, as it doest not implies the well known complexity of $O((\log(a)+\log(b))^{2}.$ Instead of trying to reinvent the wheel, you would have better to type "complexity of Euclidean algorithm" in Scholar Google and read the articles on the subject. You could also read what is said about this in The Art of Computer Programming by Knuth (chapter on semi-numerical algorithms). D.Lazard (talk) 09:26, 29 July 2017 (UTC)

@D.Lazard, Good idea, no problem to refer to "The Art of Computer Programming". I suppose you already checked it and you might have already found that the bottom of page 322 of volume 2 (p. 334 in the on-line pdf) reports a running time of "$19T+6$ [CPU] cycles, where $T$ is the number of divisions performed". The maximum value of $T$ is $O(\log N)$ at page 343, last 2 lines. Note: he uses $N=\max(a,b)$. The analysis seem to imply the division takes a constant number of cycles. If we accept this, the complexity becomes equivalent to $O(\log(a)+\log(b))$. If we don't accept this, the exact complexity depends on the complexity of the division on a chosen machine. So either we accept Knuth reports $O(\log(a)+\log(b))$ or we say the reported running time as equivalent to $O(T)$ divisions plus some other simpler operations $O(T)$ CPU cycles, where $T=O(\log(N))=O(\log(a)+\log(b))$. In the second case, the running time reported by Donald Knuth is rather closer to my statement than to others. In both cases, he is not very close to $O((\log(a)+\log(b))^{2})$. — Preceding unsigned comment added by Daniel.porumbel (talk • contribs) 12:30, 29 July 2017 (UTC)

I have not Knuth's book under hand, and, thus, I cannot verify whether you have missed some paragraph of exercise. In any case, a quick Google Scholar search lead me to this article, where the bound $O((\log(a)\log(b))$ is proved (theorem 3). This bound is equivalent with $O((\log(a)+\log(b))^{2})$ if a is close to b, and strictly better if a is much larger than b. D.Lazard (talk) 13:16, 29 July 2017 (UTC)

Action?

Based on above discussion, I see two ways to correct the article. Choosing either of them seems

like a question of personal taste to me. Please let us decide together if we should:

1. Say the Euclidean algorithm has complexity $O((\log(a)\log(b))$ (equivalent or better than $O((\log(a)+\log(b))^{2})$) according to Theorem 3 (p. 6) of this reference found by D. Lazard.
2. Give a more generic statement "$O(\log \ a+\log \ b)$ arithmetic operations on numbers with at most $O(\log \ a+\log \ b)$ bits". This is clearly polynomial in input size $\log \ a+\log \ b$ but not strongly polynomial, enough to make the point needed in the article. No reference is needed, except a link to the Wikipedia article on the Euclidean algorithm.

However, both variants are better than saying the Euclidean algorithm uses $O((\log \ a+\log \ b)^{2})$ steps on the Turing machine, which is, to the best of my knowledge (as proved above), wrong. — Preceding unsigned comment added by Daniel.porumbel (talk • contribs) 17:01, 29 August 2017 (UTC)

Apparently, David Eppstein modified the statement without telling anybody (fourbe). He put something vague that gives no clue on the magnitude of the complexity, something saying nothing particular about the Euclidean algorithm, most probably due to his lack of understanding. The current text could work well for any weakly polynomial algorithm out there, not necessarily the Euclidean algorithm.Daniel.porumbel (talk) 14:08, 21 September 2017 (UTC)

Please, respect the policy WP:Civility, and do not use personal attacks such as "fourbe", "lack of understanding". Repeating such a behavior may lead to a block (see WP:Blocking policy). Also, you can easily put this article in your watchlist. If you do that, you will be notified of every edit of the article. No other notification is needed, and your first assertion is totally wrong: Davids edit has been notified to everybody who has this article in his watchlist.

About this edit: this section is not about Euclidean algorithm but about polynomial time. Euclidean algorithm appears here only as an example. Thus this does not matter, here if the complexity is quadratic or not, And Eppstein's edit is perfectly correct. D.Lazard (talk) 14:50, 21 September 2017 (UTC)

If my remark was on somebody else, I would have been more careful. But if you pay attention, it's David Eppstein who first used "lack of understanding", although I pointed out an error that he eventually tried to correct. And he should pay attention to avoid personal attacks as much as me or anybody else. Fourbe was a copy paste error, it's not even English. By looking briefly through his page, he is involved in different edit wars, maybe you know him personally. With the current text, "Euclidean algorithm" is no longer a proper example, as we say nothing particular relating to it, we could replace it with any weakly polynomial algorithm out there. I wish I didn't point out the error in the initial version. The initial version made the point of an example of a weakly polynomial algorithm more clearly. By the way, where exactly did you find that he did announced his intention to modify the thing and explain it? If you honestly think about it (could you?), you will accept his text is too vague, much vaguer that what I or you proposed. — Preceding unsigned comment added by 163.173.231.56 (talk) 14:50, 2 October 2017 (UTC)

Why does the current text only states on the Euclidean algorithm running time that it is "bounded by a number of Turing machine steps"? Many books are far more specific.Danieldanielcolo (talk) 07:45, 20 July 2018 (UTC)

The current text is not about the complexity of Euclidean algorithm, but about the distinction between strongly and weakly polynomial time. The exact bounds of complexities do not belong to this section, and can be found, for example, in Euclidean algorithm. D.Lazard (talk) 08:28, 20 July 2018 (UTC)

I took the pain to look over previous arguments. The text does give the Euclidean algorithm as an example showing the difference between strongly and weakly polynomial. Someone argued (correctly?) the current text says nothing specific to the Euclidean algorithm; all that is said holds for any Weakly polynomial algorithm. It seems you were once unsatisfied by this kind of vagueness and you wanted to be precise using the best known results: "Your statement is not wrong, it is strictly weaker than the better known result, as it doest not implies the well known complexity of $O((\log(a)+\log(b))^{2}.$ ". You easily change your mind?Danieldanielcolo (talk) 08:44, 20 July 2018 (UTC)

The statement that the bit complexity is $O((\log(a)+\log(b))^{2}$ does not say anything about strong polynomial complexity. Thus the main statement of this section (namely that Euclidean algorithm is not strongly polynomial), is not weaker than the best known bit complexity of Euclidean algorithm. This is specific to Euclidean algorithm, as most common algorithms that are weakly polynomials are also strongly polynomial. D.Lazard (talk) 09:47, 20 July 2018 (UTC)

You are clearly following the old principle: "if you can't convince them confuse them". First, your "best known" bit complexity $O((\log(a)+\log(b))^{2}$ is wrong on the TM. It is well-known that the TM needs quadratic time only two compare two bit strings, as correctly recalled by somebody else above. Secondly, everything the current text states about the Euclidean algorithm does hold for any weakly (and not strongly) polynomial algorithm. The following is a logical consequence: giving the Euclidean algorithm here as an example of a weakly (and not strongly) polynomial algorithm in the current form is as good as nothing.Danieldanielcolo (talk) 13:26, 20 July 2018 (UTC)

Are you serious? Showing the existence of weakly polynomial algorithms that are not strongly polynomial is "as good as nothing"? D.Lazard (talk) 13:57, 20 July 2018 (UTC)

Now you take things out of context altering the meaning, resulting in mocking remarks with no argument. Yes, seriously, what I said it that is that "giving the Euclidean algorithm here as an example of a weakly (and not strongly) polynomial algorithm in the current form is as good as nothing.". Maybe you skipped "in the current form"; in the given context, "in the current form" means "as long as you say nothing particular to the Euclidean algorithm, nothing that does not hold for any weakly (not strongly) polynomial algorithm".Danieldanielcolo (talk) 14:10, 20 July 2018 (UTC)

Did David Eppstein really provide a solution or is it as good as nothing?

Applying pure logics, the above argument suggest that his "solution" is simply as good as nothing, for the above provided reason.

Quicksort

In the quasi-linear section, the statement "Its non-randomized version has a O(n log n) running time only when considering average case complexity" regarding quicksort is false. With proper pivot selection (for example, using median-of-medians), it is possible to guarantee O(n log n) worst-case runtime deterministically.

132.236.122.152 (talk) 18:06, 29 August 2018 (UTC)

Sure, but that's not the same algorithm. It's still a version of quicksort, but it's not "the non-randomized version" of the randomized quicksort discussed here. —David Eppstein (talk) 18:11, 29 August 2018 (UTC)

Is even/odd test a good example?

In the table, the example given for O(1) is "determine if an integer (represented in binary) is even or odd." Is that a good example? After all, the test is done on one integer, and doesn't reference N. How about this: "determine if an integer of N bits is even or odd" ? SlowJog (talk) 15:07, 8 September 2015 (UTC)

A better example is finding the median value in an array of sorted numbers. I made that edit. SlowJog (talk) 00:58, 29 October 2018 (UTC)

Psuedo-polynomial time should be added in table

Pseudo-polynomial time deserves a mention Wqwt (talk) 21:25, 19 April 2019 (UTC)

Linearithmic time

linearithmic adj. Of an algorithm, having running time that is O(N log N). Coined as a portmanteau of `linear' and `logarithmic' in "Algorithms In C" by Robert Sedgewick (Addison-Wesley 1990, ISBN 0-201-51425-7).

http://catb.org/jargon/html/L/linearithmic.html

Linearithmic was added to this article "10:53, 10 January 2010" by Miym

I don't think it is the purpose of Wikipedia to popularize funny word constructions invented by a creative author. Especially it should not treat this word as if they are standard terms.

WolframMathWorjd does not know this term: http://mathworld.wolfram.com/search/?query=linearithmic&x=0&y=0

So I will remove this caption.

> The current page still has this "Linearithmic" word, that nobody uses (I have never seen it used in a course, nor research paper). Further, it tries to back it up with two references, [8] and [9]: [9] is the aforementioned Sedgewick book (which invented the term, apparently for fun). The second is a paper by Naik, Regan, Sivakumar (1995) which does not contain that term anywhere. Can we remove this made-up, unused "linearithmic" word from the page altogether? Clément Canonne (talk) 21:54, 14 May 2020 (UTC)

Google scholar has "about 832" hits for "linearithmic", suggesting that your claim of non-use is false. —David Eppstein (talk) 22:37, 14 May 2020 (UTC)

832 hits, given the thousands of hits for "nearly-linear time" and "near-linear time," seems quite small. Is it enough to justify a mention in this page, especially given that one of the two references meant to back this use on that very page appears to not even use the term?Clément Canonne (talk) 23:07, 14 May 2020 (UTC)

Further, the mere fact that this term is featured on this page (and has been for 10 years) may bolster its use. To quote a comment above on this very topic (not by me): "I don't think it is the purpose of Wikipedia to popularize funny word constructions invented by a creative author. Especially it should not treat this word as if they are standard terms. " Clément Canonne (talk) 23:10, 14 May 2020 (UTC)

The term is not featured on the page. It is in boldface because it is the target of a redirect.

The comparison ot the number of hits with "nearly-linear time" and "near-linear time" is nonsensical as the terms are not synonymous. As far as I know, "nearly linear time" is either synonymous with "quasilinear time", or is not a technical term (common meaning of "nearly").

Here, the relevant questions are 1/ Is the class n log n notable enough for being listed in the WP article? 2/ Is this name a common name for this class? As far as I know, both answers are yes (832 hits may appear small, but this has to be compared to the number of articles that refer explicitely to this specific class, possibly with another name). So, I do not see any reason to remove this term, except that you don't like it, which is not a valid reason, here. D.Lazard (talk) 09:22, 15 May 2020 (UTC)

At the very least then, can someone else confirm whether the citation [8] indeed uses this term (I couldn't find the term in the paper), and if not remove that citation? This is merely factual. Clément Canonne (talk) 14:31, 15 May 2020 (UTC)

The sentence in question has two claims, one about the definition of quasilinear time and the other about the definition of linearithmic time. Its two sources are sources for its two claims. Why are you expecting the source for quasilinear to also contain linearithmic or vice versa? —David Eppstein (talk) 16:37, 15 May 2020 (UTC)

Oh, I didn't read that sentence this way. That makes sense... but wouldn't then putting the [8] earlier in the sentence be more accurate (or does it go against citing rules?)

"An algorithm is said to run in quasilinear time (also referred to as log-linear time) if T(n) = O(n logk n) for some positive constant k; linearithmic time is the case k = 1.[8][9]"

vs.

"An algorithm is said to run in quasilinear time (also referred to as log-linear time) if T(n) = O(n logk n) for some positive constant k [8]; linearithmic time is the case k = 1.[9]"

Clément Canonne (talk) 16:42, 15 May 2020 (UTC)

That would be reasonable. The reference should always go after the punctuation, though: ";[8]", not "[8];". —David Eppstein (talk) 18:12, 15 May 2020 (UTC)

OK -- I made that change. Clément Canonne (talk) 19:40, 15 May 2020 (UTC)