Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Big-O notation explained by a self-taught programmer

justin.abrah.ms

Post reply on HN
Print view View original

71–80 of 80 posts

Re: Big-O notation explained by a self-taught programmer

#71

Post by AYBABTME »

gnuvince wrote: post #69
YZF wrote: post #32

The math of Big-O isn't that hard and the article while having good intentions misses the point. Big-O is about asymptotic behaviour and the graphs are misleading in that regard (well, they're simply wrong, not misleading). There are algorithms where if you just look at the Big-O you'd think one has faster run time than the other but because the constants fall out that wouldn't be the case for any practical problem s…

I think that Sedgewick's tilde notation [1] is nice if you want to include more information about constant factors. [1] http://algs4.cs.princeton.edu/14analysis/

His tilde notation is also more informative than the big-O one. The canonical example is Quicksort. If you look at its big-O time complexity, it's O(n^2). When for all practical cases, it's ~n log n.

Re: Big-O notation explained by a self-taught programmer

#72

Post by ceol »

Ixiaus wrote: post #51
eksith wrote: post #46

Earlier quoted context omitted.

but the idea that Big O is "scary" is just absurd. To you. I never studied things like these in school and getting to a point of "Oh that's what that means" was long and arduous as it pertained to a lot of scientific literature. Plain English, it seems, isn't in the tool set for a lot of very smart people who, coincidentally, feel that it's their duty to Explain All the Things . It's unfortunate that so many of them…

I'm as autodidactic as they come (high school drop out, self-taught in math, comp sci, psychology) and I to think this is elementary stuff. The correct way to "understand these things" is to learn the math, the theory, and do the exercises. Would you take a scientist seriously if they didn't understand what the scientific method was? You're right. English is not the tool to use here in explaining theory, it's not cap…

As an aside, you can't be self-taught in psychology. It's like being a self-taught doctor: Being educated in psychology is predicated upon you having a degree in psychology, because it's a very certification-heavy field.

I would actually advise you to not brag about being "self-taught in psychology" because it's a very strong indicator that you don't know what you're talking about.

Re: Big-O notation explained by a self-taught programmer

#74

Post by twoism »

ericholscher wrote: post #37
YZF wrote: post #32

The math of Big-O isn't that hard and the article while having good intentions misses the point. Big-O is about asymptotic behaviour and the graphs are misleading in that regard (well, they're simply wrong, not misleading). There are algorithms where if you just look at the Big-O you'd think one has faster run time than the other but because the constants fall out that wouldn't be the case for any practical problem s…

As a data point, I have no idea what you just said.

This is the only useful comment in this entire thread.

Re: Big-O notation explained by a self-taught programmer

#75

Post by kyllo »

tsahyt wrote: post #66
kyllo wrote: post #39

Earlier quoted context omitted.

He's saying that big O only matters for big input sizes, because big O is specifically about the algorithm's asymptotic performance, which means its performance for a large value of n. If you have a small value of n then the other constant time operations in the algorithm may affect the running time more. n^2 is less than n^3 right? But is 2 * n^2 + 100 less than n^3? Depends on how big n is, right? Big O notation ju…

More or less, yes. What he is saying is that there is a constant hidden in the big O. Say, we have two algorithms A and B with a runtime that can be bounded by the functions a(n) = 1000n^2 and b(n) = 0.001n^3 respectively. Hence a ∈ O(n^2) and b ∈ O(n^3). So the first algorithm A is clearly faster asymptotically. However, suppose we have input sizes of around n=50000, it actually turns out that algorithm B is faster…

The definition of a "big" input size is somewhat circular, yes.

"The big O performance of an algorithm only matters for a sufficiently large value of n."

"Define a sufficiently large value of n."

"Large enough that the big O performance of the algorithm starts to matter more than the coefficients of n and constant time operations."

So yes, that could be 10 or 10 million depending on the nature of the problem, the constants and coefficients of the algorithm, the language, the hardware, etc etc. You could have an algorithm that takes factorial time but maybe you're only using it in a problem domain where n is always < 10 so you'll probably never notice or care that it's O(n!)

Re: Big-O notation explained by a self-taught programmer

#76

Post by Ixiaus »

ceol wrote: post #72
Ixiaus wrote: post #51

Earlier quoted context omitted.

I'm as autodidactic as they come (high school drop out, self-taught in math, comp sci, psychology) and I to think this is elementary stuff. The correct way to "understand these things" is to learn the math, the theory, and do the exercises. Would you take a scientist seriously if they didn't understand what the scientific method was? You're right. English is not the tool to use here in explaining theory, it's not cap…

As an aside, you can't be self-taught in psychology. It's like being a self-taught doctor: Being educated in psychology is predicated upon you having a degree in psychology, because it's a very certification-heavy field. I would actually advise you to not brag about being "self-taught in psychology" because it's a very strong indicator that you don't know what you're talking about.

So...you're claiming that because something is certification heavy I can't be self-taught!?!?!?! Jungian psychology, freudian psychology, alchemical symbolism; ALL disciplines of personal understanding and understanding inter-personal relationships that have spanned hundreds of books on my bookshelf and years worth of self-application to become a happier more effective human being. I guess none of that was worth it because I don't know what I'm talking about!

Oy I might as well stop reading books then because claiming I'm self-taught in anything will make me look bad! No offense, but your comment made you look like you don't know what you are talking about. How can you seriously say to someone they shouldn't call themselves self-taught/educated in anything based on your criteria?

What the fuck would you call self-education then if reading books, becoming more intelligent, applying it to your life, and improving quality of said life isn't self-education? Self-education is something everyone does, even people that have been through a formal education. The difference is that they are choosing their subjects of study instead of having them chosen.

By the way, your analogy would be stronger if I laid claim to "psychiatry" rather than "psychology" - psychiatry is more akin to being a doctor; I do not ever claim to practice what I know on other people just as people that love studying physiology and medical text-books don't practice on people!

Oh, also, I was not bragging, I was qualifying myself for the commenter as someone who is self-taught so I wouldn't appear to be someone that doesn't know what they are talking about.

Re: Big-O notation explained by a self-taught programmer

#77

Post by Ixiaus »

eksith wrote: post #53
Ixiaus wrote: post #51

Earlier quoted context omitted.

I'm as autodidactic as they come (high school drop out, self-taught in math, comp sci, psychology) and I to think this is elementary stuff. The correct way to "understand these things" is to learn the math, the theory, and do the exercises. Would you take a scientist seriously if they didn't understand what the scientific method was? You're right. English is not the tool to use here in explaining theory, it's not cap…

It's unfortunate you've read my post as a claim to avoid actually learning these. I was pointing out that the "x is elementary" attitude doesn't help the process and I thought (from the video at least) some empathy in communication is warranted. It's ridiculous to expect clarity when no such thing exists in the language used to describe an idea in the first place. The OP went to the trouble of making such a post. May…

Well, I must still be misunderstanding you because I spent 30 minutes writing a whole comment explaining why Math is important then got to the bottom of your comment and realized we both believe the same thing (that these subjects are important).

What I will contend is that pity parties about scary topics are unhelpful and rigor is important - more so for self-taught people. Like you, I advocate humane teaching. Humane teaching, to me however, is more about adapting to learning styles while maintaining the rigor and difficulty of the material (without watering it down) - this article watered it down.

Clear and humane explanations are out there; this article was not one of them. The intention was noble and I respect them for that but I agree with the top commenter in that the pity party needs to end and more self-educated individuals need to be role models for those that do find it scary so that we can all (as in self-educated people) strive to understand difficult concepts instead of "being okay" with not fully understanding it or the language it was meant to be understood in.

Much as autodidactic scholars hold themselves up to very high standards when reading about an author, they read the author's works in the original language they were written in - not in its translations (this is slight speculation because I don't know any autodidactic scholars personally, but I have read some of their articles).

Re: Big-O notation explained by a self-taught programmer

#78

Post by eksith »

Ixiaus wrote: post #77
eksith wrote: post #53

Earlier quoted context omitted.

It's unfortunate you've read my post as a claim to avoid actually learning these. I was pointing out that the "x is elementary" attitude doesn't help the process and I thought (from the video at least) some empathy in communication is warranted. It's ridiculous to expect clarity when no such thing exists in the language used to describe an idea in the first place. The OP went to the trouble of making such a post. May…

Well, I must still be misunderstanding you because I spent 30 minutes writing a whole comment explaining why Math is important then got to the bottom of your comment and realized we both believe the same thing (that these subjects are important). What I will contend is that pity parties about scary topics are unhelpful and rigor is important - more so for self-taught people. Like you, I advocate humane teaching. Huma…

Then it seems, we're basically on the same page.

Watering down is unacceptable. No argument here. What I do appreciate though is that advanced topics can be made reachable with a step stool, at least at first, before the full rung up the ladder.

That "being okay" with not fully understanding a concept grates me to no end too.

It's honestly incredibly condescending. That said, there are ways to be more clear without being condescending and without accepting that "okay" is good enough.

Take that math, for example. I've lost count of how many people I've run into who hate Calculus and the like because "it's so hard!" This tells me that the approach to teaching it was all wrong. I hated math too, cause it was big and scary, until I came across and awesome teacher who actually sat down with me and went over the basics with very careful attention to the language she used. There are approaches to teaching like this online I'm sure, but they're very few and far between.

Re: Big-O notation explained by a self-taught programmer

#79

Post by anonymoushn »

jfarmer wrote: post #55
baddox wrote: post #50

Earlier quoted context omitted.

It sounds to me like you're mixing up two things: "worst case performance" and "asymptotic performance." You say > Big-O is concerned with worst case performance. Colloquially, f∈O(g) means that "Eventually, f performs no worse than g." Aren't these two different concepts? Worst case performance deals with the worst possible input of any given input size (like pathological inputs to Quicksort), while asymptotic perfo…

Let's be precise. I'm being more precise here in my comment than I was on Quora. Big-O and related notations are ways of categorizing functions. O(n^2) for example is actually a set of functions, which is why I wrote f ∈ O(n^2) rather than something like f = O(n^2) or f(n) = O(n^2). That is, f is a member of some set of functions which all satisfy a particular, precisely-defined property. To understand that property,…

f∈Θ(g) is equivalent to f∈O(g)∧g∈O(f). This isn't really a "tight upper bound." For your spikey function f above, we have f∈O(n^2) and f∈Ω(n). These bounds are tight in the sense that there are no strictly tighter bounds. That is, there exists no function g with f∈O(g)∧g∈o(n^2) (there is no function asymptotically smaller than n^2 that bounds f from above). So for this f one could reasonably consider n^2 to be a "tight upper bound", although one would need to pick a spikey bounding function to say anything involving f and Θ.

The problem of having an infinite number of inputs of size n is usually not a problem, because there are finitely many bit strings of each length. If an algorithm uses subroutines that act on input objects of unbounded length (like comparing arbitrary-precision integers), and you are only interested in the bound for the number of subroutine calls, then there might be some trouble with the notion of an average case across a fixed input size. This is a bit silly though; it's more a way to define "fixed input size" into describing "unboundedly large input size" than something I would actually want to do for some useful purpose.

Re: Big-O notation explained by a self-taught programmer

#80

Post by jfarmer »

anonymoushn wrote: post #79
jfarmer wrote: post #55

Earlier quoted context omitted.

Let's be precise. I'm being more precise here in my comment than I was on Quora. Big-O and related notations are ways of categorizing functions. O(n^2) for example is actually a set of functions, which is why I wrote f ∈ O(n^2) rather than something like f = O(n^2) or f(n) = O(n^2). That is, f is a member of some set of functions which all satisfy a particular, precisely-defined property. To understand that property,…

f∈Θ(g) is equivalent to f∈O(g)∧g∈O(f). This isn't really a "tight upper bound." For your spikey function f above, we have f∈O(n^2) and f∈Ω(n). These bounds are tight in the sense that there are no strictly tighter bounds. That is, there exists no function g with f∈O(g)∧g∈o(n^2) (there is no function asymptotically smaller than n^2 that bounds f from above). So for this f one could reasonably consider n^2 to be a "tig…

Er, well, I was using the function as an example of something which is f∈O(n^2) but not f∈Θ(n^2) under the assumption that when the OP reads the symbols "f∈O(n^2)" he's really thinking something more like f∈Θ(n^2).
Post reply on HN