Remix clone Hacker News

new | show | ask | jobs Github

▲

suddenlybananas 6 days ago

>Big O notation also suffers from this - it's almost useless for real world problems.

It's not the only way to optimize things but there's a reason no one sorts with bubble sort.

▲

Sankozi 6 days ago | parent | next [-]

Yes bubble sort usually will take more time, but big O notation does not say that quick sort will be better for your real world problem.

Complexity estimations or just benchmarks are much better at that.

You should never limit yourself to big O notation when comparing algorithms.

	▲	suddenlybananas 6 days ago \| parent [-]
		>You should never limit yourself to big O notation when comparing algorithms. Sure, but it's still an incredibly useful tool for considering how your algo will scale.

▲

LegionMammal978 5 days ago | parent | prev [-]

Not quite bubble sort, but many recursive sorting implementations will switch to an O(n^2) algorithm like insertion sort once they reach a small number of elements. Simple but poorly-scaling methods usually have a place as base cases of hybrid algorithms.

In other news, there's a reason no BLAS implementation multiplies matrices with Strassen's algorithm, and it's not that the people writing those are too dumb.

	▲	Al-Khwarizmi 5 days ago \| parent [-]
		Still, in quicksort, big O notation analysis is what tells you that you can further improve efficiency by leaving small subarrays unsorted and then performing a single call to insertion on the whole array at the very end, rather than one insertion call to sort each individual small subarray. This result is far from obvious without big O analysis. So still useful, even there.