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

WTF Is Big O Notation?

rob.conery.io

Post reply on HN
Print view View original

71–80 of 101 posts

Re: WTF Is Big O Notation?

#71

Post by roel_v »

robconery wrote: post #55
roel_v wrote: post #12

(Warning: nerd sniping incoming) The main problem with this article is that it doesn't stress (or even mention, as far as I can tell) that it's performance characteristics at the margins . Meaning, it's about a generalized operation on a very large data set. Your fancy hashing algorithm might be slower than just doing a linear scan over a 10-element table, not to mention the maintenance of your tree structure. In the…

OP here. Big O is indeed "worst case scenario" always, the size of the data set doesn't matter. An O(n) operation doesn't care if the data is sorted - even if it's the first item as you suggest. When you discuss Big O it's always worst case.

Well that's not what your article is saying - it says (well, not in these words, but it's at least what I got from it) that it's meant to be something practical to understanding algorithmic complexity and how that relates to code performance. And for that, the size of the data and the details of the algorithm very much do matter. Throughout these comments, people seem to be using two 'concepts' of big O and because of that, talking past each other: the academic 'provable upper boundary' concept and the applied 'what algorithm or data structure should I choose for my concrete problem, and how does complexity help me decide' concept. That last one is what is colloquially known as 'big O analysis', whereas technically that term is reserved for something else indeed. I'll readily admit that when I first made my GP comment, I didn't really clearly make that distinction in my mind either, which is probably what is the real underlying issue I was trying to point out.

Re: WTF Is Big O Notation?

#72

Post by jhanschoo »

gpm wrote: post #38

This seems like a good time to bring up one of my pet peeves about big O notation. Every theoretical model I've ever seen says that indexing into n bits of memory takes O(1) time. That's obviously impossible: - The pointer you need to read is log(n) bits. - The physical memory is at best O(n^(1/3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it's probably O(n^(1/2)) becaus…

In industry there is indeed a hand-waving of the size of addressing. IMO for industry this is not too important since a lg n multiplicative factor is peanuts.

With respect to the space problem, for some problems researchers don't care about it so much because it only means that it is a polynomial factor slower. For problems where the degree of the polynomial is important, theorists typically work with variants of Turing machines and need to specify which variant they are using, which typically do not allow random access, so this does not become important. Of course, random-access Turing machines are also studied that violate the physical constraint you mentioned.

Re: WTF Is Big O Notation?

#74

Post by LifeLiverTransp »

roel_v wrote: post #12

(Warning: nerd sniping incoming) The main problem with this article is that it doesn't stress (or even mention, as far as I can tell) that it's performance characteristics at the margins . Meaning, it's about a generalized operation on a very large data set. Your fancy hashing algorithm might be slower than just doing a linear scan over a 10-element table, not to mention the maintenance of your tree structure. In the…

Also not mentioned, hardware pyramid makes fools of people who just expect the O-Notation to be the outcome of measured performance. A cache optimal - Algorithm thats worser in the 0-Notation might still outperform a bad implementation of a O-Notation superior algorithm.

TL,DR; Knowing Big-O does not detach you from physics.

Re: WTF Is Big O Notation?

#75

Post by enedil »

bogomipz wrote: post #64
enedil wrote: post #48

Earlier quoted context omitted.

Nah, every algorithm that is O(N logN) is also O(n^2). That would be a sign, that you as an interviewer didn't fully grasp Big O.

Nah "f(n) is said to be in O( g(n) )" formally speaking but practically speaking an algorithm in some production code that runs in O(n log n) vs one that runs in O(n^2) are not the same thing at all. That would be a sign that you as a candidate are being needlessly pedantic and usually a red flag.

You're confusing O with Theta.

Re: WTF Is Big O Notation?

#76

Post by Grue3 »

bogomipz wrote: post #17

>"My rule of thumb here is that if I have to use a loop within a loop, that’s O(n^2)." This might potentially do someone a disservice. The whole point of analysis is just that - to "analyze" the runtime and not resort to "rules of thumb." The presence of nested for loops itself is not a good reason to declare something quadratic. Consider the following which is most certainly not O(N^2): for (int i = 0; i for (int j…

Big-O is an upper bound. Something that's O(n) is also O(n^2).

Re: WTF Is Big O Notation?

#77

Post by hackerpacker »

LifeLiverTransp wrote: post #74
roel_v wrote: post #12

(Warning: nerd sniping incoming) The main problem with this article is that it doesn't stress (or even mention, as far as I can tell) that it's performance characteristics at the margins . Meaning, it's about a generalized operation on a very large data set. Your fancy hashing algorithm might be slower than just doing a linear scan over a 10-element table, not to mention the maintenance of your tree structure. In the…

Also not mentioned, hardware pyramid makes fools of people who just expect the O-Notation to be the outcome of measured performance. A cache optimal - Algorithm thats worser in the 0-Notation might still outperform a bad implementation of a O-Notation superior algorithm. TL,DR; Knowing Big-O does not detach you from physics.

Nor the realities of various languages. I've seen hashes break down exponentially with "big data". (inb4 "then it wasn't a 'true' hash). There are countless variables beyond "+ x"

If it is important, then you test/profile it. Otherwise it isn't important, and this is mostly theory crafting.

Re: WTF Is Big O Notation?

#78

Post by OrgNet »

roel_v wrote: post #12

(Warning: nerd sniping incoming) The main problem with this article is that it doesn't stress (or even mention, as far as I can tell) that it's performance characteristics at the margins . Meaning, it's about a generalized operation on a very large data set. Your fancy hashing algorithm might be slower than just doing a linear scan over a 10-element table, not to mention the maintenance of your tree structure. In the…

in this context, n = n/2 ... because the performance difference is not that great.

Re: WTF Is Big O Notation?

#79

Post by gaze »

Oh ffs another article about Big-O without the actual definition anywhere in it. Put it at the end after motivating it, put it at the beginning and then explain it, I don’t care. Just actually give it at some point.

Re: WTF Is Big O Notation?

#80

Post by mannykannot »

LifeLiverTransp wrote: post #74
roel_v wrote: post #12

(Warning: nerd sniping incoming) The main problem with this article is that it doesn't stress (or even mention, as far as I can tell) that it's performance characteristics at the margins . Meaning, it's about a generalized operation on a very large data set. Your fancy hashing algorithm might be slower than just doing a linear scan over a 10-element table, not to mention the maintenance of your tree structure. In the…

Also not mentioned, hardware pyramid makes fools of people who just expect the O-Notation to be the outcome of measured performance. A cache optimal - Algorithm thats worser in the 0-Notation might still outperform a bad implementation of a O-Notation superior algorithm. TL,DR; Knowing Big-O does not detach you from physics.

This is an important consideration in practice, and I think it would be helpful if classes teaching O-notation would include an exercise that makes this point. It is also true, however, that O-notation considerations always dominate for large enough problems.

Anyone expecting the O-Notation to give the outcome of measured performance has made a category error, as it is never about run-time itself, it is about the change of run-time with problem size (and only in the asymptopic limit).

Post reply on HN