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

31–40 of 101 posts

Re: WTF Is Big O Notation?

#31

Post by [deleted] »

roel_v wrote: post #23
opportune wrote: post #16

Earlier quoted context omitted.

NO. BIG O notation is not average unless specified as such! It is an equivalence class of the provable upper bound on the execution time of the algorithm on an arbitrary input. There are algorithms like quick sort where average runtime != “big O of quicksort”

Sure that's what it is formally, but that's not the applied meaning the article is about. Take an hypothetical search algorithm that is O(1) except when the container you're searching is of length 50, then it's O(n). That makes the algorithm O(n), right? (yes this is a stupid contrived example, and I know one can make any case when one can make up any reality etc. - but I think it's a valid style figure in this case,…

[deleted]

Re: WTF Is Big O Notation?

#32

Post by derekp7 »

eindiran wrote: post #5
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…

That's not my experience as a software engineer at all. In fact, I would say that I see people worrying about writing algorithms that are asymptotically optimal (well before that should ever be a consideration) 10x as often as I see people failing to consider the efficiency of the algorithms they write.

Do you think this is due to a difference between working at a place that has software requiring a specific non-computer related skill set (such as medical diagnostics software), vs being at a place that hires primarily CS grads for regular software? Other developers that I've worked around at previous jobs were in manufacturing (Informix 4GL devs), and an IT services company, among others. The one common thread I've seen though is they tend to be impressed by what I can do in C, for example, or helping them get to the root of an issue they have (I will typically reverse engineer what they are doing from the outside looking in, using things like strace, then writing up an analysis of what I see from the systems side).

Another recent example is a case where the app needed to start a number of sub-processes. So the dev used an equiv of a system() call, which spawned a bash shell, to do a ps -ef |grep process_name |grep -v grep |grep -v vi |grep -v vim |grep -v less, to see if the process was running, then doing another system() call to start the sub process. The whole string would be repeated for each sub process, and then they wondered why it took 8 minutes to start all their sub interfaces when they deployed to a larger customer that needed 700 interfaces started (instead of the typical 20 - 50). Oh, and after they would start an interface, the code would do the "ps..." commands on all the other interfaces to update an internal table on their status.

Re: WTF Is Big O Notation?

#33

Post by joshuamorton »

roel_v wrote: post #23
opportune wrote: post #16

Earlier quoted context omitted.

NO. BIG O notation is not average unless specified as such! It is an equivalence class of the provable upper bound on the execution time of the algorithm on an arbitrary input. There are algorithms like quick sort where average runtime != “big O of quicksort”

Sure that's what it is formally, but that's not the applied meaning the article is about. Take an hypothetical search algorithm that is O(1) except when the container you're searching is of length 50, then it's O(n). That makes the algorithm O(n), right? (yes this is a stupid contrived example, and I know one can make any case when one can make up any reality etc. - but I think it's a valid style figure in this case,…

No, that algorithm is O(1).

50 is a constant. As n -> infinity, the algorithm runs in constant time.

Specifically, I can pick some number C such that C * f(n) > the number of operations, then the algorithm is O(f(n)).

So I choose f(n) == 1, and C == 100.

Then the runtime of the algorithm is 1,1,1,1,1...., 50,1,1,1,1,.... For all values of n, this is less than C * f(n) == 100, a constant, so it is O(f(n)). f(n) is 1, so it is O(1).

Re: WTF Is Big O Notation?

#34

Post by roel_v »

c3534l wrote: post #20
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…

> What does happen is that 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). You're conflating theta and omega notation for big O. Big O is the worst case scenario. The average or even typical operation doesn't matter. If the algorithm is the most complex when sorting a list of items that were already sorted in descending…

Fair enough, when looking at the academic origin and defintions; but googling a bit and looking at articles like https://medium.com/@.RT/total-n00bs-guide-to-big-o-big-%CF%8... (under 'The Big Caveat', third paragraph), I feel validated in my assertion that your 'Big theta' is what is in practice and colloquially is known as 'Big O', and is also what this article is talking about.

(But I'll admit that I had mostly forgotten about this distinction, and certainly couldn't tell which one is which without looking it up)

Re: WTF Is Big O Notation?

#35

Post by anon946 »

bogomipz wrote: post #26
anon946 wrote: post #21

Earlier quoted context omitted.

Well, as written, it is 'O(1)'. Or did you mean to put N instead of 1000?

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.

Yes, but my point is that, as written, there is no dependency on N. Thus, O(1).

Re: WTF Is Big O Notation?

#36

Post by [deleted] »

imtringued wrote: post #11
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…

It doesn't sound like teaching Big O Notation would help your coworkers write faster software. You would be better off by teaching them how to use databases properly.

[deleted]

Re: WTF Is Big O Notation?

#37

Post by enedil »

roel_v wrote: post #18
worik wrote: post #15

Earlier quoted context omitted.

...an algorithm or data structure operation described as being 'O(n)' could really be 'O(n) + x' No it should not. (O(N) + x) is O(N). That is how it works, is spoken about... What it means! It is a very simple minded article, and IMO misleading, but it is better than "(O(N) + x) is bigger than O(N)". In the sense of order analysis, it is not.

Well yes, that's what I said, although I guess I could have used 'n + x operations' to keep it consistent with the article and still in line with the formal definition.

Yeah, you really could have. It also grinds me when people will say "it's O(n), not O(n^(3/2))", because the former is a subset of later, not to mention talking about worst case/average case/best case. Big O notation has nothing to do with probabilities, literally nothing.

Re: WTF Is Big O Notation?

#38

Post by gpm »

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)) because we build on flat planes (once you start talking about petabytes of data anyways).

Maybe this doesn't matter in practice, because the constants associated with these are small enough (but are they, how many memory/disk bound applications are there? How much extra performance could we squeeze out by using 16/32 bit pointers for small arrays?). It certainly doesn't matter in theory where things work like we say they do regardless of the physical reality. But it annoys me that it's so obviously wrong.

Re: WTF Is Big O Notation?

#39

Post by vecter »

bogomipz wrote: post #26
anon946 wrote: post #21

Earlier quoted context omitted.

Well, as written, it is 'O(1)'. Or did you mean to put N instead of 1000?

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.

It's a subtle point, but anon946 was pointing out that since your loops are fixed at 1000, this entire thing is O(1) (granted, with a large constant). You should change all of the "1000" to "n". That would make it O(n lg n).

edit: you've now edited the inner loop to be n, but the outer loop is still 1000. This is still wrong, as the entire algorithm is now just O(lg n).

Re: WTF Is Big O Notation?

#40

Post by roel_v »

joshuamorton wrote: post #33
roel_v wrote: post #23

Earlier quoted context omitted.

Sure that's what it is formally, but that's not the applied meaning the article is about. Take an hypothetical search algorithm that is O(1) except when the container you're searching is of length 50, then it's O(n). That makes the algorithm O(n), right? (yes this is a stupid contrived example, and I know one can make any case when one can make up any reality etc. - but I think it's a valid style figure in this case,…

No, that algorithm is O(1). 50 is a constant. As n -> infinity, the algorithm runs in constant time. Specifically, I can pick some number C such that C * f(n) > the number of operations, then the algorithm is O(f(n)). So I choose f(n) == 1, and C == 100. Then the runtime of the algorithm is 1,1,1,1,1...., 50,1,1,1,1,.... For all values of n, this is less than C * f(n) == 100, a constant, so it is O(f(n)). f(n) is 1,…

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

Post reply on HN