Is 2n+constant a good big o notation for a sorting algorithm?
I have an assignment in a comp sci class to develop the fastest sort possible and found this to be the big o notation for my algorithm. The constant is based off the highest value in the sort.

Recommended Answers

Is 2n+constant a good big o notation for a sorting algorithm?

Yes, that's excellent relative to the usual suspects such as quicksort and mergesort, and it hints at the algorithm as well because comparison-based sorting algorithms have a hard bottom of Omega(nlogn). If you've dropped into linear territory your algorithm …

Jump to Post

All 2 Replies

Is 2n+constant a good big o notation for a sorting algorithm?

Yes, that's excellent relative to the usual suspects such as quicksort and mergesort, and it hints at the algorithm as well because comparison-based sorting algorithms have a hard bottom of Omega(nlogn). If you've dropped into linear territory your algorithm must be distribution-based similar to a bucket sort.

Getting linear time is impossible unless you have some hard limit on the size of the values you're sorting. If you do have such a limit, than linear time is ordinary.

Your algorithm is probably not good if it is what I think it is, since it'll be full of cache misses.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.