11–20 of 80 posts
I don't know first thing about math, but even I find that the classical definition (i.e. that find in the CLRS book) is pretty straightforward: given an input big enough, the running time will be at most that of a multiple of function g(n) if f(n) = O(g(n)), where f is the function that describes the algorithm's running time.
I think you meant "constant" multiple of g(n)
I don't know first thing about math, but even I find that the classical definition (i.e. that find in the CLRS book) is pretty straightforward: given an input big enough, the running time will be at most that of a multiple of function g(n) if f(n) = O(g(n)), where f is the function that describes the algorithm's running time.
> at most that of a function multiple I think you meant "constant" multiple of g(n)
This sort of contributes to giving self-taught programmers a rather bad name. The writeup is good, but the idea that Big O is "scary" is just absurd. It's an elementary concept that every working programmer should be familiar with, regardless of whether they're self-taught. Algorithms are not "scary". If you can't reason about algorithms, you may not be a very good programmer yet. To be clear, I really appreciate the…
This sort of contributes to giving self-taught programmers a rather bad name. The writeup is good, but the idea that Big O is "scary" is just absurd. It's an elementary concept that every working programmer should be familiar with, regardless of whether they're self-taught. Algorithms are not "scary". If you can't reason about algorithms, you may not be a very good programmer yet. To be clear, I really appreciate the…
Ahh yes. Let's berate the OP for being intimidated by a topic and then diving in and learning it on their own. This will really encourage others to learn on their own and contribute back.
Not trying to berate the OP. I'm trying to say I wish OP had framed it better.
Nice writeup! That said, I got ~500 gumballs in the machine ((container diameter / gumball diameter)^3 * .64) so both guesses of 100 and 1000 should be within an order of magnitude. ;)
So rounding 500 to the nearest order of magnitude gives 1000. 310 is the mid point.
This sort of contributes to giving self-taught programmers a rather bad name. The writeup is good, but the idea that Big O is "scary" is just absurd. It's an elementary concept that every working programmer should be familiar with, regardless of whether they're self-taught. Algorithms are not "scary". If you can't reason about algorithms, you may not be a very good programmer yet. To be clear, I really appreciate the…
I think computer science has a bad wrap for being useless brain-teasers used only in interviews (within a subset of the target demographic of this article). Through the bits I've managed to pick up, I feel like they contribute to a better understanding of programming on a broader spectrum.
While you may not see a body of knowledge that many people expect you to know (that you don't know) as scary, I can assure you that many people do. There are many similar topics that induce some amount of fear in me still: issues around multi-threading and race conditions, cryptography, deep understanding of networking stacks, and compilers to name a few.
I'd also like to point out some of the phrasing you've chosen. 'the idea that Big O is "scary" is just absurd' -> 'If you can't reason about algorithms, you may not be a very good programmer'. This is the source of fear among self-taught programmers (and the source of my own fear in the above examples). We all want to be good at what we do, so let's try to lift each other up! :)
O(N) is read "Order of N" because the O function is also known as the Order function. I think this is because we're doing approximation, which deals in "orders of magnitude". It's a different meaning of "order", that has to do with the shape of the size-vs-time curve. It's the same meaning as the order of a polynomial ("x" is linear or 1st order, "x^2" is quadratic or 2nd order, etc). but Big-O is all about the appro…
This is a nice explanation, but I couldn't help but notice that the estimate of the number of gumballs in the pictured machine seems closer to 1000 than 100 (contrary to the claim in the article). You can actually see about 100 gumballs in the picture, so there must be far more hidden behind them -- my guess is closer to 500, which is about twice as close (in order-of-magnitude) to 1000 as to 100.
Unfortunately, there are some misconceptions that are propagated in this article. Kudos on the effort, but some statements are just flat out wrong, such as this statement: "Big-O is all about the approximate worst-case performance". Big-O has nothing to do with worst-case, but is a bounding function. An O(n) algorithm is also O(n^2), O(2^n), etc. Those are valid bounds on the O(n) algorithm, just not the smallest.
Speaking of worst-case (or best-case, average-case, etc.) scenarios, how does big O notation relate? The variables inside an O() notation as far as I know refer only to the size of the input, so when we say that finding a value in an unsorted list is in O(n), we're referring to the worst-case scenario (obviously, finding a value in a list when that value is the head of the list is constant time, and not very interesting). Of course, that's a simplistic example, but with more complex algorithms like Quicksort, when we say it's in O(n log n) we're talking about average-case. Is this just because we know that worst-case performance in Quicksort is exceedingly rare so we don't bother mentioning that O(n log n) is average-case unless we're studying it more deeply?
This sort of contributes to giving self-taught programmers a rather bad name. The writeup is good, but the idea that Big O is "scary" is just absurd. It's an elementary concept that every working programmer should be familiar with, regardless of whether they're self-taught. Algorithms are not "scary". If you can't reason about algorithms, you may not be a very good programmer yet. To be clear, I really appreciate the…
Thanks for the comment. I don't feel as though self-taught programmers have a bad name. I feel like they can lack some skills because the importance of them aren't lauded in their social circles. It wasn't until 5 years into my professional career that I was fortunate enough to work with someone with a computer science background, so the topics of Big-O never even came up. I think computer science has a bad wrap for…
The work you're doing is wonderful. The problem I had with it is that a simple modification to it (not phrasing it in a condescending way toward self-taught programmers) would've made it so much better.