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

91–100 of 101 posts

Re: WTF Is Big O Notation?

#91

Post by mixmastamyk »

derekp7 wrote: post #32
eindiran wrote: post #5

Earlier quoted context omitted.

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…

I don't think one needs to be a CS grad to recognize such a poor design.

Re: WTF Is Big O Notation?

#92

Post by mixmastamyk »

toadi wrote: post #22

I mostly don't think about it too much. If I have a piece of code that seems slow I make it less complicated and mostly look up the big-O. Reason is that I only had a few time in my 20 year career that I really had issues with this.

True, after a few years of experience you recognize pitfalls to avoid. I remember figuring this out on my own as a kid writing a chat client, years before learning O terminology. As the number of clients reached ten performance dropped and quickly realized I needed to handle the situation more efficiently and did.

Doesn't provide the smug satisfaction of using the academic notation/jargon given in tech interviews and hn threads however.

Re: WTF Is Big O Notation?

#93

Post by vecter »

bogomipz wrote: post #81
enedil wrote: post #75

Earlier quoted context omitted.

You're confusing O with Theta.

No I am most certainly not. Nowhere did anything I said in the comment above indicated I was referring to both a lower AND upper bound which is Big Theta. Honestly it sounds as if you might not understand the difference between Theta and O. I understand that a function that is O(N^2) grows no faster than O(N^3) asymptotically speaking however the intention of my original comment and example is quite clear about their…

You most certainly are confusing O with Theta. O is just an asymptotic upper bound. Of course a function that’s bounded by n lg n is also bounded by n^2.

Re: WTF Is Big O Notation?

#94

Post by bogomipz »

vecter wrote: post #93
bogomipz wrote: post #81

Earlier quoted context omitted.

No I am most certainly not. Nowhere did anything I said in the comment above indicated I was referring to both a lower AND upper bound which is Big Theta. Honestly it sounds as if you might not understand the difference between Theta and O. I understand that a function that is O(N^2) grows no faster than O(N^3) asymptotically speaking however the intention of my original comment and example is quite clear about their…

You most certainly are confusing O with Theta. O is just an asymptotic upper bound. Of course a function that’s bounded by n lg n is also bounded by n^2.

No I am not. The other commenter inexplicably and needlessly decided to introduce Theta and assert that I was confused.

Maybe you might reread my original comment. This whole side discussion is of no value to my original comment which has a very clear and very narrow context.

I am not sure why the both of you want to belabor some ancillary talking point that you yourselves decided to introduce. It is of exactly no value to the context of my original comment and not in the least bit productive.

Re: WTF Is Big O Notation?

#95

Post by enedil »

School-Cotton wrote: post #87
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”

This is completely wrong. Big O has nothing to do with algorithms. Big O notation can be used for any mathematical function from an ordered set to another ordered set, including average runtime of an algorithm as a function of data size, worst-case runtime of an algorithm as a function of data size, guaranteed amortized runtime of an algorithm as a function of data size, or anything else (including things with nothin…

To be honest, this is false too. You need functions with values that can be multiplied by scalars. If you just have ordered set, then you can't account for this constant from the definition. Alternatively, you could say that values of the function need to be from a normed vector space (but I'm not sure if it can be extended furthermore. Maybe normed C-module?)

Re: WTF Is Big O Notation?

#96

Post by [deleted] »

TheCoelacanth wrote: post #86
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, it's best-case O(1), worst-case O(n) (technically O(1) since there is a constant upper-bound, but let's pretend you said it's O(n) when length is divisible by 50 instead of equal to 50) and average-case O(1). Each of those functions has its own big O, without specifying which function you are talking about big O isn't meaningful.

[deleted]

Re: WTF Is Big O Notation?

#97

Post by School-Cotton »

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.

This is wrong. Big-O can be used to talk about any function you like, whether best case of an algorithm, worst case, average case for uniform inputs, average case over some different distribution of inputs, how many branch mispredicts a Skylake core hits while running the code on backwards sorted input, the median price of a Big Mac as a function of a country's GDP per capita, or anything else.

Re: WTF Is Big O Notation?

#98

Post by School-Cotton »

jhanschoo wrote: post #72
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 Tur…

Actually the size of indices can be important in real life. For example, on Nvidia GPUs, a kernel that indexes data with 64-bit indices will usually be much slower than one that uses 32-bit indices.

(Hard to argue that this is related to big-O since there are only two data points, but I'm just pointing out that index size is in fact a real-world concern).

Re: WTF Is Big O Notation?

#99

Post by School-Cotton »

enedil wrote: post #95
School-Cotton wrote: post #87

Earlier quoted context omitted.

This is completely wrong. Big O has nothing to do with algorithms. Big O notation can be used for any mathematical function from an ordered set to another ordered set, including average runtime of an algorithm as a function of data size, worst-case runtime of an algorithm as a function of data size, guaranteed amortized runtime of an algorithm as a function of data size, or anything else (including things with nothin…

To be honest, this is false too. You need functions with values that can be multiplied by scalars. If you just have ordered set, then you can't account for this constant from the definition. Alternatively, you could say that values of the function need to be from a normed vector space (but I'm not sure if it can be extended furthermore. Maybe normed C-module?)

Sure, but that doesn't change my point.

Re: WTF Is Big O Notation?

#100

Post by giucal »

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…

I think they don't matter because:

1. they are all fixed or bounded quantities;

2. all algorithms are subject to them.

On the other hand, in practice, the input size is also bounded. You deal not with arbitrarily long arrays, for example, since memory is not infinite.

So, I think, asymptotic time complexity is meaningful as long as the inputs we are considering can grow so much -- while remaining bounded -- that a linearithmic algorithm indeed outperforms, say, a quadratic one for a large and relevant class of inputs.

And that may be why computational models make those assumptions; but I'm not remotely sure.

Post reply on HN