If you only want to hire me based on answering big-O questions I don't want to work there anyway. 32 years of working on highly complex and performant stuff and not once did I think in terms of big-0. Optimizing is not about knowing the math but knowing how to measure and how to interpret what you measure. Big-O might make you feel smart but it's a tiny part of actually constructing something complex and optimal.
Big-O Algorithm Complexity Cheat Sheet
131–136 of 136 posts
Re: Big-O Algorithm Complexity Cheat Sheet
#132If you only want to hire me based on answering big-O questions I don't want to work there anyway. 32 years of working on highly complex and performant stuff and not once did I think in terms of big-0. Optimizing is not about knowing the math but knowing how to measure and how to interpret what you measure. Big-O might make you feel smart but it's a tiny part of actually constructing something complex and optimal.
I mostly agree. big-O knowledge helps you pick the right data structures and algorithms for the job. The idea is that it will often help you avoid having to rediscover all those complexity classes by trial and error when looking at systemtap traces or time stamps in the log stream.
For example in real-time systems picking a btree vs a hash based data-structure might work better sometimes since there is a less of a chance of a sudden spike related to hash re-sizing, instead there is a small penalty to be paid during insertion. I believe that. Have I actually measured that? No. Because it would involve re-writing a bunch of code and it would take time. So I don't know if big-O had saved my ass here.
That is just one example.
Or say when when it comes to large data storage, knowing the base data structure used in the database will give you some expectation as to how it behaves when the size grows.
All that said, it is hard to point back in 7+ years and say, aha, I know exactly how many times knowing big-O saved me from spending extra time and effort debugging. I can think maybe only of one or two times recently when I had to think about big-O so I mostly agree with you.
It certainly seems that not knowing anything about big-O will not terribly handicap someone who knows how to use debugging and profiling tools. There are probably other more practical bits of knowledge that are more important to know.
Despite this these kind of questions are very popular. I see a few reasons. 1) "Big Company" interviews. Big companies love hiring fresh college grads from good schools. Those don't have a lot of relevant software development experience. But they have to be selected and tested somehow so theoretical CS is the goto tool. 2) Other companies just copy the interview questions from big company interviews thinking "well they are so big and successful because they are using these kind of questions to select candidates". Whether it is true or not, I don't know but I believe that processes goes on behind the scenes.
Re: Big-O Algorithm Complexity Cheat Sheet
#133You can pass some interviews by blindly memorizing, but it's unnecessary. If you understand a concept, then you can reason its big O. Memorization implies a superficial understanding that may be revealed later. If you don't understand something, spend a few hours and implement it. "I hear and I forget. I see and I remember. I do and I understand." - Confucious
Agree, buy a good book (for example Cormen), learn the algorithms and implement them to get a good understanding. Try to use the table to answer a following question: what is a time complexity for finding a next item (according to a key) to a given one in a hash table? Memorizing such stuff does not make much sense, but if you understand basic concepts, you will figure it out quickly. There are basic errors in the ta…
$81 for http://www.amazon.com/Introduction-Algorithms-Thomas-H-Corme...
No legal DRM free option as far as I can see.
Fifth link was a direct to the PDF.
Re: Big-O Algorithm Complexity Cheat Sheet
#134You should create an empty version of the cheat sheet so people can test their understanding of various data structures and algorithms.
Re: Big-O Algorithm Complexity Cheat Sheet
#135Earlier quoted context omitted.
What if you do not use this for an interview, butalready have a job that doesnt require you to apply this every day? I know a lot of these algorithms, but not all. I hardly ever need them, but when I do this might be a good starter to browse from. thinking cheat sheets are only for interviews is limited. I would say knowing everything from head is useless with todays internet. Have a solid base, understand a few and…
> thinking cheat sheets are only for interviews is limited I never even used the word "interview", are you sure you're responding to the correct comment?
true, the interview part was for large discussion above. The general concept of my reply applies to your comment though. I think your statement is a bit harsh. Or im misinterpretting what you are trying to say. Saying cheatsheets are useless is not correct imho.
Re: Big-O Algorithm Complexity Cheat Sheet
#136If you want to visualise big O runtime, you draw it on a log-log scale. The linear gradient on the log-log plot is the factor. i.e. if its at 45 degrees its O(n), if its at a gradient of 2:1 its O(n^2). Handy fact to work out your big O without having to do the tedious math! (See http://jcsites.juniata.edu/faculty/kruse/cs2/ch12a.htm )
Is this correct for n * lg n? The n * lg n on the plot has gradient that is about halfway between n and n^2, but in reality n * lg n ∈ O(n^1.00000000000000000001)