programming

wifienyabledcat, 7 months ago in Big O notation is about what matters when the numbers get big.

god i wish i had this image when i was learning algorithms. i always just guessed for some of the exam questions 🙃

HarkMahlberg, 7 months ago in Big O notation is about what matters when the numbers get big.

Aren't the most commonly accepted sorting algorithms O(nlog(n))? Quicksort? Mergesort? Those are considered bad?

cawifre, 7 months ago

I mean, it is entirely reasonable that “bad” is the best performance you can hope for while sorting an entire set of generally comparable items.

If you can abuse special knowledge about the data being sorted then you can get better performance with things like radix sort, but in general it just takes a lot of work to compare them all even if you are clever to avoid wasted effort.

Kajo, 7 months ago

Yeah, you’re right, it doesn’t make sense to say that O(f(n)) is good or bad for any algorithm. It must be compared to the complexity of other algorithms which solve the same problem in the same conditions.

duncesplayed, 7 months ago

I mean…yeah. Just because something is provably the best possible thing, doesn’t mean it’s good. Sorting should be avoided if at all possible. (And in many cases, such as with numbers, you can do better than comparison-based sorts)

ericjmorey, 6 months ago

The labels are from the perspective of viewing the space of all possible functions of element set size to operations, so they don’t apply to any particular problem an algorithm is attempting to solve (that space is often smaller).

tranzystorek_io, 6 months ago in AoC Input fetch tool (Rust)

Nicely done! I have a CLI tool that does sth similar (input download, answer submissions): github.com/tranzystorekk/arrive