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.
geeknick -3 Newbie Poster
Narue 5,707 Bad Cop Team Colleague
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.
Rashakil Fol 978 Super Senior Demiposter Team Colleague
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 developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.