The thing I always run into when discussing big-O are people (good programmers even) who think all O(x) algorithms have the same efficiency. I find it very frustrating when someone says my streamlined O(N) algo with 5 operations has the same efficiency as their O(N) algo with 20 extra function calls and operations. Big-O is not the only determining factor...
Big-O notation explained by a self-taught programmer
21–30 of 58 posts
Re: Big-O notation explained by a self-taught programmer
#22Don't you want to know if your recipe takes 10 minutes or 10 hours to cook?
Sometimes. Sometimes you just need to throw things in the oven until the first one browns up. I recently had a problem where I needed an adjacency matrix of shortest paths. It was a choice between dijkstra and floyd-warshall. My dijkstra implementation kicked the pants off of floyd warshall for this application by an order of magnitude, which you wouldn't really expect. And the big-O complexity was the same for both…
A few comments just in case this a critical part of your program, and if running it faster would help:
1. Using a heap with Dijkstra's algorithm would speed up your program
From your comment I am guessing you are using Dijkstra's algorithm without a heap, which gives O(n * m) for one source, and O(n^2 * m) for all sources (all pairs shortest path), where n is the number of nodes/vertices, and m is the number of edges
You would be able to improve that to O(m * n * lgn) by using a heap, which improves the time to run it by quite a lot in practice
2. The time it takes to run the program also depends on the density of your matrix:
In the case where the graph is sparse: m ~ n, and will result in O(n^2 * lgn) (or O(n^3) without a heap)
In the case where the graph is dense: m ~ n^2, and will result in O(n^3 * lgn) (or O(n^4) without a heap)
Compare the numbers above to O(n^3), which is the time complexity of Floyd-Warshall
So just in terms of time complexity, Floyd-Warshall would be faster in a dense graph
Re: Big-O notation explained by a self-taught programmer
#23Don't you want to know if your recipe takes 10 minutes or 10 hours to cook?
> Don't you want to know if your recipe takes 10 minutes or 10 hours to cook?
Yes, the first time, then it becomes a skill learned from experience.
I started learning Big-O a few months back and I have been working as a programmer for several years, not knowing about Big-O didn't stop me from becoming a lead of a development team. Knowing about Big-O is important but humans learn more from experience (aka. trail and error) than anything else. I started learning about Big-O just because I am interviewing right now and many tech companies love to ask those questions, but if I were not interviewing I would probably leave that topic for another time.
Re: Big-O notation explained by a self-taught programmer
#24Earlier quoted context omitted.
How can anyone applying for a programming job not know Big-O notation? That's CS101. I don't care if you're self-taught, it's audacious to even call yourself a programmer if you don't know the very basics of algorithms and data structures. If I were interviewing a candidate, and it was revealed he didn’t know Big-O notation, my next questions would be about data structures, because now I’m suspecting he wouldn’t even…
How can anyone applying for a programming job not know Big-O notation? That's CS101. You pointed out exactly how someone would not know -- they may have never taken computer science classes and taught themselves programming. Or they may have taken some CS classes, not enough to have covered that particular concept. I'd guess that, especially for older programmers, anecdotally, it's not uncommon to not really understa…
But still you had to hear about it sometimes, somewhere, it's mentioned in pretty much any serious text on algorithms. Thing is that many people see it mentioned, but never bother to stop & learn what it's all about... and that's telling something about their approach to programming (and life) in general.
Re: Big-O notation explained by a self-taught programmer
#25As a self-taught, I always get nervous when I see articles explaining Big O because they are almost always wrong. While this one is mostly correct, it is a bit simplistic and misleading, and it could use considerable annotations. The "scary" Wikipedia article has examples that are more nuanced than what is written here; the first example shows a constant time algorithm with nested for loops. I take issue with the mat…
As a self taught programmer who did no math in university, the most valuable thing to me was the discovery that the math really isn't scary. Once you understand the symbols and notation, most concepts are rather easy, given you commit time to learning it.
I strayed away for so long until I watched the MIT lecture series on algorithms and it all just clicked. The best feeling was was seeing the math on the chalk board for how you determine the complexity of operations on various graph layouts and just getting it. I struggled in high school math and rarely got that feeling in class.
It was just one of those, "holy crap... It's all just an array and how we organize the data in that array that gives various benefits and drawbacks!" Incredibly empowering.
Edit: This is the series I watched: https://www.youtube.com/watch?v=HtSuA80QTyo&index=1&list=PLU...
Re: Big-O notation explained by a self-taught programmer
#26Didn't know that the "O" in Big-O actually means "order". I guess it doesn't really matter too much.
If you really wanted to get theoretical, you could also talk about the whole family, including little-O, big-omega, little-omega, etc. :)
Re: Big-O notation explained by a self-taught programmer
#27Earlier quoted context omitted.
> "That makes sense. Big-O notation is so overrated." Can you explain how having a classification that allows one to determine whether something is logarithmic vs vs quadratic is so overrated? Isn't that a bit like saying "Algebra is so overrated"? Also Donald Knuth introduced Big O somewhere around the mid 1970s and C++ didn't come along until 1979. https://en.wikipedia.org/wiki/Big_O_notation#cite_note-knuth... Als…
The thing is that an O(n) algorithm can perform faster than an O(1) algorithm simply because Big-O is only comparing different scenarios on a single routine and not how it compares to other algorithms. A slow algorithm might technically be O(1) but that doesn't necessarily make it fast.
Yes, however big O notation isn't about which programs run faster, it's about how the runtime of a program changes in response to the input size
Re: Big-O notation explained by a self-taught programmer
#28Don't you want to know if your recipe takes 10 minutes or 10 hours to cook?
Yes, testing is critical.
Re: Big-O notation explained by a self-taught programmer
#29My company always works a "Big-O" question into interview questions. It's funny how we ask about the complexity of the algorithm and maybe 50% of applicants even know what Big-O notation is. It doesn't seem to impact hiring decisions though. We haven't turned anyone down because they miss that question. I think it's because anyone who has programmed for a year or so professionally already understands the concept of i…
That makes sense. Big-O notation is so overrated. A little bit of history: C++ programmers were always able to choose the right containers simply by using this image, since long before the invention of Big-O. http://homepages.e3.net.nz/~djm/containerchoice.png
Tip: If you're asked about Big-O in an interview, and your rusty, at least determine whether the algorithm is sub-linear or super-linear. Just knowing this is 80% of what you need to be aware of in industry IMHO.
Re: Big-O notation explained by a self-taught programmer
#30Earlier quoted context omitted.
I can't agree more, when interviewing I always ask this kind of questions of "theoretical knowledge" not to have the actual answer, but to see how candidates reacts when they don't know. Because if the guy not only admits he does not know directly and is eager to know what it is briefly, then you know that giving your team and environment is favorable to learning, the guy will soon be able to catch up, and it's certa…
How can anyone applying for a programming job not know Big-O notation? That's CS101. I don't care if you're self-taught, it's audacious to even call yourself a programmer if you don't know the very basics of algorithms and data structures. If I were interviewing a candidate, and it was revealed he didn’t know Big-O notation, my next questions would be about data structures, because now I’m suspecting he wouldn’t even…
Depends on the role, for junior devs my company doesn't care if you have ever programmed before. If the person is clever, we can teach them to program. For example, the most recent hire has a masters in maths from oxford, he may have never seen Big-O, but he could certainly understand it if need be.