Nov-06-2018, 06:40 PM
Hello,
I had a test today and I lost my points on one question.
The book we are using in the class says:
O - runtime complexity
Ω - lower bound
exchange sort = O(n²), Ω(n²)
selection sort = O(n²), Ω(n²)
insertion sort = O(n²), Ω(n)
bubble sort = O(n²), Ω(n)
quick sort(Hoare) = O(n²)(in most cases - O(n log n)), Ω(n)
merge sort = O(n log n)
bucket sort = O(n)
(for some algorithms there are no Ω written in the book)
Question is: Is exchange sort algorithm the easiest of all algorithms for sorting(written in book)?
I answered NO, because bucket sort has complexity O(n) and exchange sort has O(n²).
After test I was looking through the book and I found this statement without further explanation:
"Exchange sort is the easiest of all algorithms for sorting"
My final question is: Have I answered it wrong or is this some mistake in the book?
P.S.
Firstly, sorry for my bad English. I tried my best to translate terms used in the book.
Secondly, it wouldn't be the first mistake in that book. I found some mistakes earlier.
Thanks in advance,
hrca
I had a test today and I lost my points on one question.
The book we are using in the class says:
O - runtime complexity
Ω - lower bound
exchange sort = O(n²), Ω(n²)
selection sort = O(n²), Ω(n²)
insertion sort = O(n²), Ω(n)
bubble sort = O(n²), Ω(n)
quick sort(Hoare) = O(n²)(in most cases - O(n log n)), Ω(n)
merge sort = O(n log n)
bucket sort = O(n)
(for some algorithms there are no Ω written in the book)
Question is: Is exchange sort algorithm the easiest of all algorithms for sorting(written in book)?
I answered NO, because bucket sort has complexity O(n) and exchange sort has O(n²).
After test I was looking through the book and I found this statement without further explanation:
"Exchange sort is the easiest of all algorithms for sorting"
My final question is: Have I answered it wrong or is this some mistake in the book?
P.S.
Firstly, sorry for my bad English. I tried my best to translate terms used in the book.
Secondly, it wouldn't be the first mistake in that book. I found some mistakes earlier.
Thanks in advance,
hrca