I always get big and little oh mixed up.
Big-O notation explained by a self-taught programmer
21–30 of 80 posts
Re: Big-O notation explained by a self-taught programmer
#22This 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 the "scary" part is the notation. Any competent programmer, whether schooled or self-taught, is familiar with the concepts if not the notation.
Re: Big-O notation explained by a self-taught programmer
#23Unfortunately, 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.
Note that there are other bounding functions, like bounded from the bottom (which still isn't the same thing as worst-case). See https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachm... . 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 val…
The average case for finding a value in an unsorted list is also O(n). Assuming the values you want are randomly distributed, on average you have to look at half the list. Naively this sounds like O(n/2), but O(n/2) is actually the same as O(n) because you strip out the constant factor of 1/2.
Re: Big-O notation explained by a self-taught programmer
#24Earlier quoted context omitted.
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…
I understand where you're coming from, but unfortunately employers read articles like these and use them as justification to solidify their notion that self-taught programmers are less knowledgeable or less reliable than their peers with degrees, and hence should be paid less or not be hired at all. I've experienced it firsthand. You may argue "that's not a place you'd want to work at anyway," but unfortunately in a…
You keep repeating this, but that doesn't make it true.
Where I've worked and hired people -- in San Francisco and Silicon Valley -- there is little emphasis placed on formal eduction. Virtually none. Some companies have a reputation for liking degrees. Google, for example, but they are an exception.
I don't think a self taught programmer, who takes his craft seriously and learns not just practical how-to but also data structures and algorithms, is at ANY disadvantage in today's job market.
Re: Big-O notation explained by a self-taught programmer
#25O(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…
And when talking about the running time of an algorithm with O-notation, concerns about whether or not an algorithm is faster by a constant factor (for example three times faster, an order of magnitude faster, two orders of magnitude faster) compared to another algorithm is not captured by the O-notation by convention (it is abstracted out, so to speak). If you find out that an algorithm is O(2n), you simplify it to O(n) (the coefficient of n does not matter).
Re: Big-O notation explained by a self-taught programmer
#26Earlier quoted context omitted.
I understand where you're coming from, but unfortunately employers read articles like these and use them as justification to solidify their notion that self-taught programmers are less knowledgeable or less reliable than their peers with degrees, and hence should be paid less or not be hired at all. I've experienced it firsthand. You may argue "that's not a place you'd want to work at anyway," but unfortunately in a…
You keep repeating this, but that doesn't make it true. Where I've worked and hired people -- in San Francisco and Silicon Valley -- there is little emphasis placed on formal eduction. Virtually none. Some companies have a reputation for liking degrees. Google, for example, but they are an exception. I don't think a self taught programmer, who takes his craft seriously and learns not just practical how-to but also da…
Well, you work in SF / SV. There's a whole Earth outside of those places. And those places are largely prejudiced against people who don't have degrees. I've experienced it firsthand.
"Well, move!" Except it's not that easy when you have family.
Re: Big-O notation explained by a self-taught programmer
#27Earlier quoted context omitted.
Note that there are other bounding functions, like bounded from the bottom (which still isn't the same thing as worst-case). See https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachm... . 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 val…
The average case for finding a value in an unsorted list is also O(n). Assuming the values you want are randomly distributed, on average you have to look at half the list. Naively this sounds like O(n/2), but O(n/2) is actually the same as O(n) because you strip out the constant factor of 1/2.
Of course. But it's also the worst case. I'm really just wondering if there's a "default" scenario that's being referred to when we just say "f(n) is in O(n)" or does it depend on context?
Re: Big-O notation explained by a self-taught programmer
#28This 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…
Being familiar with big O notation is not that same thing as being familiar with a few basic complexity classes. I wouldn't be surprised or disappointed if a self-taught programmer was intimidated by big O notation, but I would be surprised if they were unfamiliar with the concept that hash map lookups are much faster than array searches, or that searching a sorted array is much faster than an unsorted array. You seem to be using "big O notation" to refer to fundamental competency about basic data structures. It's even quite possible and understandable for a self-taught programmer to, over time, figure out that certain big O classes refer to certain algorithms while still not understanding the meaning of the mathematical notation.
Re: Big-O notation explained by a self-taught programmer
#29Earlier quoted context omitted.
The average case for finding a value in an unsorted list is also O(n). Assuming the values you want are randomly distributed, on average you have to look at half the list. Naively this sounds like O(n/2), but O(n/2) is actually the same as O(n) because you strip out the constant factor of 1/2.
Of course. But it's also the worst case. I'm really just wondering if there's a "default" scenario that's being referred to when we just say "f(n) is in O(n)" or does it depend on context?
It depends on context. Generally if people fail to specify, they mean average case, as in "Quicksort takes O(n*lg n) time". There may even be some amortization shenanigans thrown in there, as in "list.append takes O(1) time".
Re: Big-O notation explained by a self-taught programmer
#30Earlier quoted context omitted.
The average case for finding a value in an unsorted list is also O(n). Assuming the values you want are randomly distributed, on average you have to look at half the list. Naively this sounds like O(n/2), but O(n/2) is actually the same as O(n) because you strip out the constant factor of 1/2.
Of course. But it's also the worst case. I'm really just wondering if there's a "default" scenario that's being referred to when we just say "f(n) is in O(n)" or does it depend on context?
Quicksort is the exception, in my experience big-O usually refers to worst case running time as opposed to average case or expected running time. CLR(S) [1] sticks to worst case because 1) worst case is a guarantee; 2) the worst case can be frequent; 3) the average case is often roughly as bad as the worst case. This is a widely used textbook, so I generally assume a lot people follow its conventions.
[1] https://mitpress.mit.edu/books/introduction-algorithms (Introduction to Algorithms)