[xyience]

I also don't see why one would necessarily need to reason from complexity arguments, rather than more intuitive "I'm using a set because I want to use set operations like union and membership". If performance is crucial, reasoning by complexity analysis is not sufficient and often not even necessary.

[jacobevelyn]

This becomes tricky when you're using a language like Ruby where arrays also have built-in union and membership operations.

And I don't see why, if performance is critical, knowing which operations/techniques/algorithms are orders of magnitude slower than others wouldn't be useful (it has been for me).

[xyience]

With higher level languages it's even less important to know theoretic complexities, just represent the problem in the most natural representation and optimize later. (You're already giving up orders of magnitude in exchange for dev time by using a higher level language.) Good engineering practices like being able to swap out structures and algorithms later matter a lot more.

Operations/techniques/algorithms are great to know when performance is critical, the subset knowledge of worst-case time and space complexities not really. (And in interviews do you ask for best case or average-under-certain-probability-distributions cases? How expansive is the trivia matrix you get candidates to fill in?) They can sometimes help guide, but they'll just as often mislead. Bubble sort and insertion sort are both n^2 algorithms, but you should never use bubble sort, and if you never profile you'll be confused why my quicker quicksort uses insertion sort inside when n is small since quicksort is n * log(n) so it should always be better right? (Conveniently ignoring worst case for quicksort is n^2 because people usually just memorize the n * log(n) factoid.) Or you'll be confused why I don't use quicksort at all if I have multiple CPU cores to create a parallel algorithm on. Throw in other aspects of modern hardware like caches (try swapping the loop order in code that needs to loop over all cells in an NxM matrix and note how much performance can suffer if you do it wrong) and branch prediction and special instructions your CPU architecture supports, those are very good to know too if you care a lot about performance. For complexity analysis in the real world, "constants matter", but that doesn't really capture all of the caveats.

Maybe the classic case of my overall point is the existence of https://en.wikipedia.org/wiki/Simplex_algorithm#Efficiency

Edit: one interview problem I like to give (given I have to give one and can't do things my preferred way) is the jump game: https://leetcode.com/problems/jump-game/ Rot13 commentary: Bar fbyhgvba vf whfg qrcgu-svefg frnepu. Va Clguba zl pbqr sbe gung vf 12 yvarf, vg hfrf n fgnpx (jvgu n abezny clguba neenl; vg pna or n dhrhr gbb vs lbh whfg punatr gur nethzrag gb .cbc()) naq n frg, ohg lbh pbhyq whfg hfr n cynva neenl sbe rirelguvat. V yvxr guvf ceboyrz fvapr vg yrgf zr frr vs gur crefba xabjf ubj gb nccyl bgure fgehpgherf orfvqrf cynva neenlf. N ybg bs crbcyr pna erpnyy gur rkvfgrapr bs frgf naq dhrhrf naq znlor svyy va gurve pbzcyrkvgvrf bs PEHQ bcrengvbaf ba n zngevk ohg pna'g npghnyyl nccyl gurz be nal nytbevguzf orlbaq ovanel frnepu naq gur onfvp PEHQ vzcyrzragngvbaf sbe rnpu onfvp fgehpgher.