Follow

some charts about computational complexity i've just come across.

like them because i find them pretty clear

i don't know pretty much about this topic. if you've studied it, do you think it's a good overview?

Show thread

@ekaitz_zarraga i guess i think there's a lot to learn about it because there are many data structures and algorithms, so there are a lot of combinations to consider.

i might study about the simplest ones some day. it sounds logical if you think about it for a moment

@jartigag Yes, there are many options to consider but learning the concept is easy and you don't need to get crazy learning all the classic algorithms, just use them and be aware of the cost when you are developing your own.

@jartigag @ekaitz_zarraga This is basically a type of math, doesnt get more logical than this ;)

@jartigag its an awesome overview... super cool.. thanks for sharing :blobaww:

@jartigag Its not bad, but it leaves a bunch of stuff out. For example, big-o complexity doesnt really matter if you have few elements. Thats why some search algorithms switch to a different algo which is supposed to be less efficient for small sets, because it is actually faster.

@felix why is faster? i mean, how to determine which will be better for small sets?

@jartigag You benchmark it. Big-O complexity is something really theoretical, it doesnt have a lot to do with reality, unless you work with huge datasets.

I learned this stuff in university, and I didnt need it a single time in my life as programmer .

@felix @jartigag Big-O notation, by its nature, reduces the actual scaling equation to only a single term and removes "small" terms. N^2 is bigger than 25N when N=100, but when N < 25, N^2 is smaller.

The reason why, e.g., sorting with insertion sort is faster than merge sort for small lists, is that computers are good at moving blocks of memory so rotations aren't *quite* as slow as might be expected, and pushing and popping the stack to recurse isn't so fast.

@jartigag one of the things i learned how to do in my CS class was calculating big o from the code itself

haven't done any complicated ones yet though, that's probably for my algorithms class
Sign in to participate in the conversation
Mastodon

Server run by the main developers of the project 🐘 It is not focused on any particular niche interest - everyone is welcome as long as you follow our code of conduct!