4 ms·
What's interesting is that an algorithm is presented as correct, but which blows up to quadratic behavior given the right input, and since since quicksort uses
by RcouF1uZ4gsC 8y ago
What's interesting is that an algorithm is presented as correct, but which blows up to quadratic behavior given the right input, and since since quicksort uses than tail recursion, could potentially cause a stack overflow. Thus you have a correct, safe algorithm in theory but not in practice.
- 14113 8y agoWhich, of course, depends on what you consider to be a "safe" algorithm.
- AzzieElbab 8y agoCould you explain about tail-rec causing stack overflow?
- garmaine 8y agoLooks like a typo. Quick sort is binary recursive so tail call optimization wouldn’t fix it.
- empath75 8y agoThose are other things you can prove — I actually watched an idris talk where they included the complexity cost in the function and it refuses to run commands over a certain complexity.