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

61–70 of 101 posts

Re: WTF Is Big O Notation?

#61

Post by mbell »

robconery wrote: post #56
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…

> time complexity and performance are the same thing

By definition, they are not.

> Mathematically the log n is always faster :)

No, it's not. Time complexity only gives you an asymptotic bound on the number of 'operations', it tells you nothing about what the actual run time will be.

Re: WTF Is Big O Notation?

#62

Post by sidlls »

User23 wrote: post #6
derekp7 wrote: post #3

My experience, as someone who isn't a professional full-time developer (systems engineer / devops focused), but who personally geeks out on CS theory, is I find it fairly rare for developers that I work with that think of Big O considerations when writing their code. A prime example, was a piece of code that has to process incoming results that get stuck in a transnational database table. Instead of selecting, then p…

One of the things I like about the C++ STL is once you learn the idioms, the API tells you whether an operation is "fast." I don't really care if a line programmer can give me the formal definition of O(x), but I sure want him to know if an operation is appropriate to call in a loop. That's speaking as a professional. As someone who finds CS fascinating, I'm appalled by the lack of interest many professional develope…

Why are you appalled? As a physicist I'm not appalled by the lack of interest most engineers have in fundamental theory that I know inside out. The reason is precisely because I understand there's a difference between practical applications and theoretical inquiry.

Re: WTF Is Big O Notation?

#63

Post by roel_v »

robconery wrote: post #59
roel_v wrote: post #51

Earlier quoted context omitted.

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) .

Yes I know that - was this reply meant for another comment?

Re: WTF Is Big O Notation?

#64

Post by bogomipz »

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.

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.

Re: WTF Is Big O Notation?

#65

Post by labster »

davismwfl wrote: post #9

That was a good write up, and it will help people. I come from the self taught side, and find that it is critical to know these things when you work in certain areas of a code base and once you reach a certain level. But I don't expect everyone needs to have the same level of understanding. I also find interviewers asking detailed questions about Big O and specific different algorithms just idiotic, especially the es…

Having for the most part avoided the computer science department during my earth science education, this is helpful.

I have sort of an intrinsic idea of what's going on -- self-joins can easily compare a data set with every other member of the data set, and hit O(N²). And that if your N is 5, the DB will probably going spend more time parsing SQL than executing your query, so no point in optimizing. So I don't understand or care about what the definition is, but it's useful tool to think about how slow your code can be.

Re: WTF Is Big O Notation?

#66

Post by eatbitseveryday »

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…

>> "Let’s say we have 1000 records in our film table. To find “Academy Dinosaur” our database will need to do 1000 operations (comparing the title in each row)."

> No you don't. If your table is sorted, [...] on average, to find any title, you will need n / 2 operations (so not 1000, but 500, in this example - this part is plain wrong as it's written). Of course, n / 2 is linear in n, so the complexity stays the same.

If something is sorted, search happens in O(log N) which is not linear: start with compare at N'=N/2. If "less than", go to N''=N'/2; if "greater than" go to N''=3N'/2. Etc.

If the data is not sorted, then yes, you will need N lookup operations.

Re: WTF Is Big O Notation?

#67

Post by robconery »

mbell wrote: post #61
robconery wrote: post #56

Earlier quoted context omitted.

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…

> time complexity and performance are the same thing By definition, they are not. > Mathematically the log n is always faster :) No, it's not. Time complexity only gives you an asymptotic bound on the number of 'operations', it tells you nothing about what the actual run time will be.

I believe we're talking past each other. Big O has nothing to do with "actual run time*. It doesn't care what about the number of inputs you have - just that you have them.

Mathematically, if n=1000 then log n is 10. 10 operations vs. 1000 is, theoretically and time complexity wise, faster.

Our disconnect is "actual" vs. "theoretical" and I want to stress again that Big O is purely theoretical. It's a technical adjective.

Re: WTF Is Big O Notation?

#68

Post by victorNicollet »

eatbitseveryday wrote: post #66
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…

>> "Let’s say we have 1000 records in our film table. To find “Academy Dinosaur” our database will need to do 1000 operations (comparing the title in each row)." > No you don't. If your table is sorted, [...] on average, to find any title, you will need n / 2 operations (so not 1000, but 500, in this example - this part is plain wrong as it's written). Of course, n / 2 is linear in n, so the complexity stays the same…

I believe the point was that, if your linear search happens to return your first element, you did not perform 1000 operations.

The context is a linear scan, not alternative algorithms that could make use of a sorted data set.

Re: WTF Is Big O Notation?

#69

Post by kadoban »

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.

If Big O is always worst case, you're going to have a hard time saying anything interesting or useful about quicksort, for instance, or hash tables.

You're going to be limited to "quicksort is O(n^2)" and "hash table lookup is O(n)", both of which are quite misleading.

There are good reasons that we usually look at the worst case, but big-O does not fundamentally or necessarily mean that.

Re: WTF Is Big O Notation?

#70

Post by roel_v »

victorNicollet wrote: post #68
eatbitseveryday wrote: post #66

Earlier quoted context omitted.

>> "Let’s say we have 1000 records in our film table. To find “Academy Dinosaur” our database will need to do 1000 operations (comparing the title in each row)." > No you don't. If your table is sorted, [...] on average, to find any title, you will need n / 2 operations (so not 1000, but 500, in this example - this part is plain wrong as it's written). Of course, n / 2 is linear in n, so the complexity stays the same…

I believe the point was that, if your linear search happens to return your first element, you did not perform 1000 operations. The context is a linear scan, not alternative algorithms that could make use of a sorted data set.

Yes exactly.
Post reply on HN