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

81–90 of 101 posts

Re: WTF Is Big O Notation?

#81

Post by bogomipz »

enedil wrote: post #75
bogomipz wrote: post #64

Earlier quoted context omitted.

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.

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

Please stop, you are adding nothing to the discussion.

Re: WTF Is Big O Notation?

#82

Post by eindiran »

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…

That might very well be there difference. My coworkers are almost exclusively people who studied CS, and several wrote C professionally at some point.

Re: WTF Is Big O Notation?

#83

Post by joshuamorton »

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…

So there's two ways of looking at it, the more handwavy is "my construction that treats your algorithm as a black box does only ever strictly more work than your algorithm. If mine runs in a constant number of operations, yours must as well." And certainly your algorithm runs in amortized constant time (which is a weird phrase).

The other way is to ask "what is a function"?

Normally, a sorting function is expressed as

    sort(List[Comparable]) -> List[Comparable]
your sorting function however has a different way of working. It has an additional input, the time. Now you might argue that you aren't taking the time as input, but you are...somehow. So in reality, your function has a signature

    sort(int, List[Comparable]) -> List[Comparable]
There's this extra int input which is weird, so you don't have. Computational complexity tools like O-notation don't concern themselves with such things. O notation only cares about how the runtime changes as the size of the input changes.

If the size of the int "time" is bounded (which it is, since the max is 86400), then one of the inputs is constant. It can be ignored.

Purity in this context is the idea that the function only acts on its inputs, there are no external forces that modify how it works. Pure functions are mathematical objects, impure functions aren't really.

So once you convert your construction to being pure, it becomes more clear why the function is ill-formed: you've got this extra constant size input (that runtime analysis can ignore) that you claim affects the runtime. Something is clearly amiss.

Re: WTF Is Big O Notation?

#84

Post by andreareina »

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.

And a lot of real-world implementations will use the asymptotically-inferior algorithm when the (sub)problem is small, for exactly this reason.

Re: WTF Is Big O Notation?

#85

Post by UncleMeat »

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.

Big O is not "worst case scenario". It describes an upper bound on functions. You can absolutely compute the Big O of the average case runtime of an algorithm.

Re: WTF Is Big O Notation?

#86

Post by TheCoelacanth »

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

Re: WTF Is Big O Notation?

#87

Post by School-Cotton »

opportune wrote: post #16
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…

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 nothing to do with computation -- it's perfectly reasonable to say things like x^2 + 5x + 2 is O(x^2) and just be talking about pure math with no reference to algorithms).

If someone asked "what is the runtime of quicksort in big O terms", it is ambiguous whether the answer is O(n^2) or O(n*log(n)) , since it's not clear which function you're talking about.

Re: WTF Is Big O Notation?

#88

Post by School-Cotton »

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…

Best, average, and worst case (and any other mathematical function from an ordered set to another ordered set) can all be described with big omega, theta, and O notation. The two concepts are orthogonal.

For example:

Quicksort's average-case time complexity is Omega(1), also Omega(n log(n)), Theta(n log(n)), O(n log(n)), and also O(e^n).

Its worst-case time complexity is Omega(1), also Omega(n^2), Theta(n^2), O(n^2), and also O(e^n).

Re: WTF Is Big O Notation?

#89

Post by js2 »

Formal definition from my ancient copy of Sedgewick:

A function g(N) is said to be O(f(N)) if there exist constants c₀ and n₀ such that g(N) is less than c₀f(N) for all N > N₀.

Continuing: "Informally, this encapsulates the notion of “is proportional to” and frees the analyst from considering the details of particular machine characteristics. Furthermore, the statement that the running time of an algorithm is O(f(N)) is independent of the algorithm's input. Since we're interested in studying the algorithm, not the input or the implementation, the O-notation is a useful way to state upper bounds on running time which are independent of both inputs and implementation details."

I'll also repeat this bit from the end of the analysis chapter:

Perspective:

Many of the algorithms in this book have been subjected to detailed mathematical analysis and performance studies far too complex to be discussed here. Indeed, it is on the basis of such studies that we are able to recommend many of the algorithms we discuss.

Not all algorithms are worthy of such intense scrutiny; indeed during the design process, it is preferable to work with approximate performance indicators to guide the design process without extraneous detail. As the design becomes more refined, so must the analysis, and more sophisticated mathematical tools need to be applied. Often, the design process leads to detailed complexity studies that lead to "theoretical" algorithms rather far from any particular application. It is a common mistake to assume that rough analyses from complexity studies will translate immediately to efficient practical algorithms: this often leads to unpleasant surprises. On the other hand, computational complexity is a powerful tool for suggesting departures in design upon which important new methods can be based.

One should not use an algorithm without some indication of how it will perform. [...]

Re: WTF Is Big O Notation?

#90

Post by mixmastamyk »

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…

Good information for a part II blog post. Believe it makes sense to leave it out of the first.
Post reply on HN