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

131–140 of 168 posts

Re: Big O Notation – Explained as easily as possible

#131

Post by pvg »

proverbialbunny wrote: post #128
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…

>The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation If the point is to identify the speed (or ram consumption) of algorithm, then why not check for that itself instead of the vocabulary in an interview? Why be pedantic when you can instead measure how well they would do as a developer? In an interview you can ask followup questions to see how precise their ability…

If the point is to identify the speed (or ram consumption) of algorithm, then why not check for that itself instead of the vocabulary

To some extent because the "that itself" is a deep field in its own right with its own specialized vocabulary.

Re: Big O Notation – Explained as easily as possible

#133

Post by psibi »

infogulch wrote: post #41

I noticed some comments here discussing the right prerequisite knowledge to understand big-O and friends. I propose limits. I think it would be a lot easier for someone to understand how to think about big-O if they already understood limits. Lim [x -> inf] O(f(x))/O(g(x)) If you know limits, you know you how and why you can ignore all but the highest power term, how to compare and simplify other kinds of terms, etc.…

I don't think limits is a good way to understand it because of the reasons here: https://math.stackexchange.com/a/3222489/124772

Re: Big O Notation – Explained as easily as possible

#134

Post by ColFrancis »

WinterHoursTF wrote: post #132

I think calling it big O was a mistake. Saying worst case upper bound isn't too many words and conveys the correct meaning to people with incorrect concepts about what big O means.

Calling it big O is indeed a mistake (especially when you start using it with handwriting, o & O because difficult to distinguish).

> Saying worst case upper bound isn't too many words and conveys the correct meaning to people with incorrect concepts about what big O means

Tricky thing is, that's not what big O says. It's a statement about the asymptotic growth of a function which you can apply to a worst case.

You'd be better off using "the worst case grows as at most". The distinction is important as you are ignoring two crucial things: the non-asymptotic behaviour and the coefficient of the asymptotic behaviour.

Re: Big O Notation – Explained as easily as possible

#135

Post by ganafagol »

bonzini wrote: post #70
tshaddox wrote: post #57

Earlier quoted context omitted.

There can be appropriate levels of imprecision. Arguably all communication necessarily requires that. This is only a problem if it leads to an unnoticed miscommunication. For example, I suspect most of the time when an engineers refers to an algorithm as being in O(n^2) they intend to preclude the possibility that the algorithm is not in O(n).

Usually "average" or worst case" O(n^2) means it's really big O, while "best case" or "always" O(n log n) means big Theta.

No, that's the opposite of what parent wrote. If an engineer mentions "this makes our functions run in O(n^2)" they mean either average or worst case and actually mean theta. The interesting fact they want to express is not the upper bound but the lower bound.

Re: Big O Notation – Explained as easily as possible

#136

Post by bnegreve »

maweki wrote: post #52

What I always find a bit missing in such articles is what the n is. The author writes "If you consider "addition" to be 1 operation" and this seems kinda intuitive and is correct if we talk about normal machine integers. But adding two arbitrary integers might be somewhat linear in bit-width. And there we have it: with a fixed bit-width, this becomes a constant term. So you might not want to talk about number of inpu…

> often enough it's not really clear what a step is

The steps are basic CPU operations such as load/store and basic arithmetic operations performed on fixed width type. I.e. things a CPU can do.

> And there we have it: with a fixed bit-width, this becomes a constant term.

It makes sense because that is how the CPU works: arithmetic operations on fixed width types are performed in constant time in the CPU ALU. Adding anything below 2^32 requires the same number of cylces.

It is only confusing when you confuse basic CPU operations with basic python instructions (an arbitrary precision addition is certainly not a simple operation from the cpu perspective)

Re: Big O Notation – Explained as easily as possible

#137

Post by OakNinja »

bjeds wrote: post #26
Edmond wrote: post #13

Earlier quoted context omitted.

Agreed. The use of "Big O Notation" itself as a way of referring to algorithmic complexity seems like a misnomer, considering that the topic is about analysis rather than the notation used to express the results of such analysis. Unfortunately academic textbooks have terrible "UX", so students end up dealing with confusing presentation of topics, hence we're stuck with labels such as "Big O Notation".

I hear you. Whether I like it or not, by now big o notation has fallen into the category of "folklore" that working engineers use and abuse informally without being very precise about it. It's like the "proof by engineers induction": if some statement P(n) is true for P(0), P(1) and P(2), then P(n) is true for all n \in Z. :-) Similarly if an engineer states that algorithm has a runtime of O(f(n)) that should probabl…

Your comment reminded me of this SO answer: https://stackoverflow.com/a/185576/1502563

/* This is O(scary), but seems quick enough in practice. */

Re: Big O Notation – Explained as easily as possible

#138

Post by d0mine »

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…

> If you implement an algorithm in a high level language like Python you may get much worse runtime than you thought because some inner loop does arithmetic with bignum-style performance instead of hardware integer performance

How does it change big O? Typically, you implement "bignum" on top of "hardware integer" regardless of the language. Or do you mean that some common integer operations are implemented with suboptimal big O in CPython?

Re: Big O Notation – Explained as easily as possible

#140

Post by crashocaster »

d0mine wrote: post #138
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…

> If you implement an algorithm in a high level language like Python you may get much worse runtime than you thought because some inner loop does arithmetic with bignum-style performance instead of hardware integer performance How does it change big O? Typically, you implement "bignum" on top of "hardware integer" regardless of the language. Or do you mean that some common integer operations are implemented with subo…

For some large n, integers in the algorithm may be so large that operations on them cease to be constant time.
Post reply on HN