Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Big O Notation – Explained as easily as possible

thatcomputerscientist.com

Post reply on HN
Print view View original

31–40 of 168 posts

Re: Big O Notation – Explained as easily as possible

#31

Post by creata »

andi999 wrote: post #30
creata wrote: post #14

Earlier quoted context omitted.

That's not even close to all there is to it. Complexity analysis is a relatively young field with lots of deceptively simple unsolved problems. For a simple example of how it's a lot more than that, follow Tarjan's proof of the disjoint set's amortized time complexity[0]. It's not at all obvious, even though the disjoint set is a very simple and practical data structure. [0]: http://www.e-maxx.ru/bookz/files/dsu/Effi…

So what would be a deceptivly simple unsolved problem?

Wikipedia has a list of big-name unsolved problems in complexity theory. Most of these have very simple problem statements.

https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_c...

Re: Big O Notation – Explained as easily as possible

#32

Post by pmiller2 »

andi999 wrote: post #29
pmiller2 wrote: post #25

Earlier quoted context omitted.

Of course "hard" is relative. Because I was writing a HN post and not a "Big-O explainer," I didn't provide you with any of that prerequisite knowledge. But, the amount of prerequisite knowledge one needs to understand this is very, very little, and would easily fit in a digestible web page, provided you have some basic fluency with functions of the real numbers. And, I think that's a reasonable level of prerequisite…

The important pre knowledge is that every polynomial is dominated by its largest exponential term (for x to infty).

It's a little more than that. You need to account for the fact that n log n dominates n, but not n^2, as well. That's not hard, but you should spell it out.

This discussion is making me think that a good way to write a "Big-O explainer" would be sort of like a progressive web app, i.e. "here's the explanation with the highest level of mathematical sophistication. Click here to get some of the prerequisite knowledge." Then, the user just keeps clicking "break it down more" until either they get it or they reach the most detailed explanation.

Re: Big O Notation – Explained as easily as possible

#33

Post by mhh__ »

cgriswald wrote: post #20
bjeds wrote: post #7

If you are the kind of person that want to read an article titled "explained as easily as possible", I think you should just avoid saying the phrase "big oh" but instead talk about algorithm runtime more informally, like "quicksort has a worst case quadratic but average case n log n runtime". The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation, as Big O is just one…

For Python code, I usually just ask critics if they’ve tested it (because I have). Frequently using a built-in will be faster than a custom loop even if at the surface level you’re going over the data more than once.

Anecdotally (it was a contrived sorting benchmark so the exact numbers don't really matter), Python started off about 3 times slower than D, but and grew at what would be considered the same O() but the coefficient was enormous. To the point where a D was taking 3s for n-million arrays, Python closer to one minute.

Node was actually very impressive, roughly as fast as D's reference compiler (cutting edge optimisations maybe 2 decades ago) in release mode.

Re: Big O Notation – Explained as easily as possible

#35

Post by mhh__ »

casion wrote: post #18
pmiller2 wrote: post #15

Every one of these "Big-O explainers" says pretty much the same thing: count (or bound) the number of steps, then take the most significant term, and drop the constant associated with it. None of them explain why you take the most significant term or drop constant factors. I get why that is. You need the mathematical definition to demonstrate why that is, and most "Big-O explainers" don't want to assume any significa…

You say it isn't hard, but I have 2 graduate degrees and didn't understand your explanation at all. "Hard" is relative to prerequisite knowledge, which can vary significantly.

Admittedly I am studying theoretical physics so I am supposed to be able to, but it made sense to me?

Re: Big O Notation – Explained as easily as possible

#36

Post by alok-g »

>> If you consider "addition" to be 1 operation then ...

What if we don't? Addition on computers is an O[1] operation only because we use fixed bit-widths for numbers, e.g., a 32-bit signed integer. How would we reformulate or express algorithmic complexity if we were to talk about unbounded integer values or infinite-precision mathematics?

Re: Big O Notation – Explained as easily as possible

#37

Post by mhh__ »

andi999 wrote: post #29
pmiller2 wrote: post #25

Earlier quoted context omitted.

Of course "hard" is relative. Because I was writing a HN post and not a "Big-O explainer," I didn't provide you with any of that prerequisite knowledge. But, the amount of prerequisite knowledge one needs to understand this is very, very little, and would easily fit in a digestible web page, provided you have some basic fluency with functions of the real numbers. And, I think that's a reasonable level of prerequisite…

The important pre knowledge is that every polynomial is dominated by its largest exponential term (for x to infty).

Largest exponential? That should be monomial, right?

Anyway you can show that on the spot if you think about what the derivative of that monomial looks like

Re: Big O Notation – Explained as easily as possible

#38

Post by pmiller2 »

mhh__ wrote: post #35
casion wrote: post #18

Earlier quoted context omitted.

You say it isn't hard, but I have 2 graduate degrees and didn't understand your explanation at all. "Hard" is relative to prerequisite knowledge, which can vary significantly.

Admittedly I am studying theoretical physics so I am supposed to be able to, but it made sense to me?

Excellent!

The level I was shooting for with my brief explanation was that someone who understood limits at a calc 1 level should be able to get it with a little thinking. I do wonder, though: did you know those things before you read my comment?

Re: Big O Notation – Explained as easily as possible

#39

Post by pmiller2 »

mhh__ wrote: post #37
andi999 wrote: post #29

Earlier quoted context omitted.

The important pre knowledge is that every polynomial is dominated by its largest exponential term (for x to infty).

Largest exponential? That should be monomial, right? Anyway you can show that on the spot if you think about what the derivative of that monomial looks like

One easy way to show that more generally is that if f and g are differentiable, f(x) dominates g(x) iff f'(x) dominates g'(x), by L'Hopital's rule. Details left as an exercise for the reader.

Re: Big O Notation – Explained as easily as possible

#40

Post by mhh__ »

alok-g wrote: post #36

>> If you consider "addition" to be 1 operation then ... What if we don't? Addition on computers is an O[1] operation only because we use fixed bit-widths for numbers, e.g., a 32-bit signed integer. How would we reformulate or express algorithmic complexity if we were to talk about unbounded integer values or infinite-precision mathematics?

You'd need to know the exact details of the implementation of your arithmetic library, but it would depend on the integer in question which makes analysis a little harder so adding two numbers would become some function O(f(n, m)) where n, m are the two numbers or some property of them (length, digits etc.)
Post reply on HN