Talk:Sorting algorithm: Difference between revisions

Revision as of 16:00, 17 December 2017

Revision as of 18:21, 17 December 2017

Line 733:

: Fourth, if you want to upper bound worst case complexity, you have to prove that all instances are below the bound. If you want to lower bound worst case complexity, you just have to prove that some instance is above the bound. It's pure logic.

: Fifth, [[User:Trimutius|Trimutius]] said "I'm not really sure what the talk is about? It is pretty obvious that in all referenced literature they use Big O Notation for a particular reason. Because Ω just isn't really important.". It is true that O is much more frequently encountered than Ω but it isn't "Because Ω just isn't really important.". The fundamental reason for that is that most of the scientific articles present a result on the complexity of a problem ; hence to give an upper bound on the complexity of a problem, it is sufficient to find SOME algorithm for the problem and upper bound the complexity of this algorithm. But if you want to show that the complexity of the problem is lower bounded, you have to prove that ALL possible algorithms for this problem have this lower bound. This is a difference between "there exists one algorithm" and "for all algorithms" that makes it much more harder in general to prove lower bounds for complexity of problems. The effort to lower bound the complexity of the algorithm is usually not done, since they cannot conclude anything with it for the problem, which is the ultimate goal, and also since most of the time the only easy-to-prove lower bound an algorithm has is the trivial lower bound of Ω(n) (the algorithm must read the input). It is expected by most computer scientist that P doesn't equal NP but that is extremely hard to prove because it implies proving a superpolynomial lower bound for some NP problem and thus having to deal with all possible algorithms for this problem. The lower bound for "Comparison sorting algorithms" is really an exception because it simply uses decision trees to be proved. No not-trivial lower bound is known for ALL sorting algorithms. In general, O results are much more easier to prove than Ω results.

: Sixth, so now consider the truth value of the four sentences: S1 = "Comparison sorting algorithms require O(n log n) comparisons for worst case complexity.", S2 = "Comparison sorting algorithms require O(n log n) comparisons for best case complexity.", S3 = "Comparison sorting algorithms require Ω(n log n) comparisons for worst case complexity." or S4 = "Comparison sorting algorithms require Ω(n log n) comparisons for best case complexity.". We can translate the mathematical asymptotic notation as follows: S1 = "ALL comparison sorting algorithms require, asymptotically, up to a constant factor, at most n log n comparisons for worst case complexity.", S2 = "ALL comparison sorting algorithms require, asymptotically, up to a constant factor, at most n log n comparisons for best case complexity.", S3 = "ALL comparison sorting algorithms require, asymptotically, up to a constant factor, at least n log n comparisons for worst case complexity." or S4 = "ALL comparison sorting algorithms require, asymptotically, up to a constant factor, at least n log n comparisons for best case complexity.". S1 and S2 are false since you can design poorly some very bad comparison sorting algorithm that will repeat an arbitrary high number of times, say n^{{sup|n}}, the comparison between the first and second element before proceeding to do a merge sort for example and ultimately solving the problem of sorting. With this poor algorithm the best and worst case will not be too far apart compared to the order of magnitude of their values, and way above nlognn log(n). On the other hand, S3 is true, that's the classical result using decision trees. S4 is false since some comparison sorting algorithm may use only n-1 comparisons on already sorted input which would be the best case. Hence the only correct sentence is "Comparison sorting algorithms require Ω(n log n) comparisons for worst case complexity.". I'll let you check by yourself that "Comparison sorting algorithms require O(n log n) comparisons for whatever complexity." is also false (you can always make a poor algorithm).

: I hope I helped at least someone on this topic. Ask questions if it wasn't clear but be aware that I'm not always connected to Wikipedia so the answer may take some time. Best regards, [[User:SectionFinale|SectionFinale]] ([[User talk:SectionFinale|talk]]) 15:56, 17 December 2017 (UTC)