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

51–60 of 101 posts

Re: WTF Is Big O Notation?

#51

Post by roel_v »

joshuamorton wrote: post #42
roel_v wrote: post #40

Earlier quoted context omitted.

Yes you're right - let me modify my contrived example and say 'at exactly midnight, the complexity is O(n)'. (the cool part about contrived examples is that you can keep making things up until it fits - now I'm just hoping I didn't miss something again like the first time :) )

Still doesn't work. Waiting one minute is constant time. (to be clear, I'm going to be able to come up with a counterexample for anything you throw at me because you're assumption here is just false, in general an algorithm that is O(f) for all values except n is O(f), because you can pick a constant greater than n, no matter what the dimension n acts in is). (If you reject that and claim that just because I can cons…

Well but (I think) what you're talking about now is the complexity of the 'wrapper' function I posed, not the complexity of the hypothetical algorithm I started out with. Yes you can add an indirection that converts it back into O(1) but the original, but that wasn't the point. I think. But then again, maybe what your second paragraph is saying is exactly that? I'll admit that I lost track of things somewhere between writing my original comment, switching back and forth to my code between compiles and now being back here :)

Also, I don't understand what you mean by 'mathematically pure', but that's on my end.

Re: WTF Is Big O Notation?

#52

Post by mwfunk »

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…

Part of it is that there's very casual, conversational usages of Big O vs. much more formal usages when trying to actually quantify performance.

Conversational Big O tends to include a lot of spherical cows (https://en.wikipedia.org/wiki/Spherical_cow), because when Big O comes up in conversation, people are more likely to be talking in generalities about high level designs. More detail could be counterproductive in that context.

When someone is actually trying to quantify and predict performance of an algorithm, then the other extreme becomes desirable- the more detailed and specific the function, the better.

Re: WTF Is Big O Notation?

#53

Post by mbell »

> I don’t want to turn this into a Redis commercial, but I will say that it (and systems like it) have a lot to offer when you start thinking about things in terms of time complexity, which you should! It’s not premature optimization to think about Big O upfront, it’s programming and I don’t mean to sound snotty about that! If you can clip an O(n) operation down to O(log n) then you should, don’t you think?

The thing is, I don't care about 'time complexity', I care about performance. Big O can serve as a useful datapoint for what the performance may be, but it's only that, one data point. e.g. It's not uncommon to find that a 'worse' algorithm/data structure in Big O terms will out perform a 'better' one because the 'worse' one has better cache locality. So no I don't think you should use an O(log n) operation in place of an O(n) operation just because of Big O, what matters is which one is faster.

Re: WTF Is Big O Notation?

#54

Post by gpm »

mwfunk wrote: post #52
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…

Part of it is that there's very casual, conversational usages of Big O vs. much more formal usages when trying to actually quantify performance. Conversational Big O tends to include a lot of spherical cows ( https://en.wikipedia.org/wiki/Spherical_cow ), because when Big O comes up in conversation, people are more likely to be talking in generalities about high level designs. More detail could be counterproductive i…

Ya, I'm directly addressing non-conversational use of Big O notation here, including the areas of academia I'm familiar with and know people in.

Re: WTF Is Big O Notation?

#55

Post by robconery »

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.

Re: WTF Is Big O Notation?

#56

Post by robconery »

mbell wrote: post #53

> I don’t want to turn this into a Redis commercial, but I will say that it (and systems like it) have a lot to offer when you start thinking about things in terms of time complexity, which you should! It’s not premature optimization to think about Big O upfront, it’s programming and I don’t mean to sound snotty about that! If you can clip an O(n) operation down to O(log n) then you should, don’t you think? The thing…

OP here - Big O notation is simply shorthand math. When you're discussing things in this way, time complexity and performance are the same thing. When you care about resource usage (memory etc) that's space complexity, which is different. Either way, they're good things to understand.

>So no I don't think you should use an O(log n) operation in place of an O(n) operation just because of Big O, what matters is which one is faster.

Mathematically the log n is always faster :). Realistically... well that would be a tough one to prove, even with caching, but I say go for it.

Re: WTF Is Big O Notation?

#57

Post by robconery »

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…

OP here. Agree that thinking about code is better than using a rule of thumb, but we need to start somewhere don't we? I tried to make it clear in the post that looping over n items within an n loop is n * n.

Re: WTF Is Big O Notation?

#58

Post by robconery »

enedil wrote: post #48
bogomipz wrote: post #26

Earlier quoted context omitted.

The inner loop is log(N), it halves the value of J after every iteration. The "do something" was meant to stand for a constant time operation so that it's N log N. But my point was really that if you told an interviewer that it was O(N^2) simply because it contained nested for loops it would be a very clear sign that you didn't fully grasp Big O.

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.

OP here - O(N log N) is not O(n^2). If n is 1000 then log n is 10, which is 1000 * 10 which is 10,000. That's a bit less than 1000 * 1000.

Re: WTF Is Big O Notation?

#59

Post by robconery »

roel_v wrote: post #51
joshuamorton wrote: post #42

Earlier quoted context omitted.

Still doesn't work. Waiting one minute is constant time. (to be clear, I'm going to be able to come up with a counterexample for anything you throw at me because you're assumption here is just false, in general an algorithm that is O(f) for all values except n is O(f), because you can pick a constant greater than n, no matter what the dimension n acts in is). (If you reject that and claim that just because I can cons…

Well but (I think) what you're talking about now is the complexity of the 'wrapper' function I posed, not the complexity of the hypothetical algorithm I started out with. Yes you can add an indirection that converts it back into O(1) but the original, but that wasn't the point. I think. But then again, maybe what your second paragraph is saying is exactly that? I'll admit that I lost track of things somewhere between…

The Big O of an algorithm does not change based on data size. Even if your set had precisely 1 record in it - the code you write, if it loops over every item in the set (even if it's only one item) - is still O(n).

Re: WTF Is Big O Notation?

#60

Post by vecter »

robconery wrote: post #58
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.

OP here - O(N log N) is not O(n^2). If n is 1000 then log n is 10, which is 1000 * 10 which is 10,000. That's a bit less than 1000 * 1000.

You're wrong. n lg n grows asymptotically slower than n^2, and is thus is O(n^2). n is also O(n^2), as is 1, or even sin(n). All of this follows directly from the definition [0].

Also the fact that you're plugging numbers in for n indicates to me that you don't actually understand big O notation, which is surprising since the original article is decent.

[0] https://en.wikipedia.org/wiki/Big_O_notation#Formal_definiti...

Post reply on HN