Time complexity O(nlogn)
Which of the following sorting algorithms yield approximately the same worst-case
and average case running time behaviour in O(n log n)?
A)Bubble sort and selection sort
B)Heap sort and merge sort
C)Quick Sort and radix sort
D)Tree sort and median-of-3-quick sort
I think both option B and D are correct.Is it right?
and average case running time behaviour in O(n log n)?
A)Bubble sort and selection sort
B)Heap sort and merge sort
C)Quick Sort and radix sort
D)Tree sort and median-of-3-quick sort
I think both option B and D are correct.Is it right?
http://bigocheatsheet.com/
At least (B) is correct, because both heap sort and merge sort have O(n log(n)) average and worst case complexity.
I have never heard of tree sort, though.
https://en.wikipedia.org/wiki/Tree_sort
According to wikipedia, worst case is O(n log n) when balanced, and O(n^2) when unbalanced. So I don't think enough information is given. I would check what your textbook specifically defines a tree sort as, to see whether they define it to be balanced or not.
However, Quicksort is O(n^2) in worst case, though, even though it's very rare for that to happen. So I would say it's only (B).
At least (B) is correct, because both heap sort and merge sort have O(n log(n)) average and worst case complexity.
I have never heard of tree sort, though.
https://en.wikipedia.org/wiki/Tree_sort
According to wikipedia, worst case is O(n log n) when balanced, and O(n^2) when unbalanced. So I don't think enough information is given. I would check what your textbook specifically defines a tree sort as, to see whether they define it to be balanced or not.
However, Quicksort is O(n^2) in worst case, though, even though it's very rare for that to happen. So I would say it's only (B).
Topic archived. No new replies allowed.