A classmate in my Data Structures & Algorithms course this semester posted this link, created by @ericrowell. I'd never seen it and it instantly ended up in my bookmarks, so I wanted to pass it on:
It provides a table that gives Big-Θ and Big-O complexities for a set of common operations on range of data structures, as well Big-Ω, Big-Θ, and Big-O for various array sorting algorithms.
I'm thinking about buying the poster...
Top comments (16)
I've published a paper (Big O of Intelligence) about algorithm complexity of human-involved algorithms. Hope it would be useful for software architects.
Thats bonkers. :)
This is why I don't like big-O.
Unless you are in O(n2) or more territory, the implementation is a lot more important than the complexity.
This is one of the most valuable topic I encountered during my study.
Haha, that reminds me of the time I did by hand something similar in my notebook for my DSA course. Surely it looks neat. Personally, I would prefer it wasn't on a black background. It would have been so much easier to read 😄 But I am one of those people whose IDE is not black so perhaps that why 😄
OH!
This is a good point, of course rote memorization will not replace actual understanding, and one would hope any decent interviewer would be able to instantly tell the difference. I don't think the point of charts like these is to cheat at interviews.
That said:
This likely varies by job domain/region/experience/whatever - I've only had one interview where I wasn't asked some arbitrary academic question about a data structure I'd never need to know in practice. Technical interviews are pretty varied, and usually broken, but this sort of thing has definitely been a theme for me. Usually in the context of a challenge problem, like you said, but I've been asked to cough up and compare and contrast options to fit a problem. A huge theme of my interview experience is "okay, tell me what the Big-O of your current solution is, and then improve it given the data is constrained by whatever". Studying a chart like this helps me, at least, even though I do understand conceptually why the values are what they are.
So, yeah, I agree, that's ridiculous. I do sorta see what they're getting at though - they want to hear you talk it through. My similar example is "how many gas stations are there in the Continental US?". Who knows or cares about the answer, but a dev employer would care about how you approach the problem.
A funny tweet but practical way to remember Big O notation :).
Thanks for that cheat-sheet.