[TYPES] Is Quick Sort slower than Insertion Sort in type theories?
Y.Luo at kent.ac.uk
Tue Dec 5 09:05:24 EST 2006
I posted an email about Quick Sort few days ago. Thank you for your reply.
Insertion Sort is primitive recursion, so it is easy to program it in type
theories and the average complexity is O(n^2).
Quick Sort is not primitive recursion, so there are proofs in the program
when it is programmed in type theories. I am told that the average
complexity "might" be O(n^3), or might be worse. Please let me know if you
know of any work on this.
Dr. Yong Luo
University of Kent
More information about the Types-list