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

141–150 of 168 posts

Re: Big O Notation – Explained as easily as possible

#141

Post by maweki »

bnegreve wrote: post #136
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…

> The steps are basic CPU operations such as load/store

Only if you consider the result of a comparison as a "store" into the register. But again, comparing two objects might not be constant. The compiler I develop for my PhD, for example, uses (written in Haskell) somewhat nested sets and quite a few operations are dominated by the equality check.

> It is only confusing when you confuse basic CPU operations with basic python instructions

But the author did exactly that, when they considered addition to be constant, which is a good approximation for small integers, but wrong in python. And really, you do have to consider those intricacies, that's why I chose this example, as sets and maps in python are basically hashmaps, you can assume constant lookup, for example, if your hash function works in constant time. And again, this begs the question what the n is. Usually we would set n as the number of items in a collection for its retrieval operation. But you actually also have to consider the item being retrieved.

Re: Big O Notation – Explained as easily as possible

#142

Post by chii »

codesparkle wrote: post #115

A bad programmer solves their problems inefficiently and a really bad programmer doesn't even know why their solution is inefficient To any beginners reading this: Solving problems inefficiently does not make you a bad programmer. Most of the time, an "inefficient" solution will be good enough, and optimising for performance comes at a cost. So sit back, relax, and enjoy the journey.

And great programmers would knowingly solve a problem inefficiently, because it's easier to write and ship it to the customer, and thus prove that the problem being solved is valuable.

Re: Big O Notation – Explained as easily as possible

#143

Post by bonzini »

ganafagol wrote: post #135
bonzini wrote: post #70

Earlier quoted context omitted.

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.

I mean you say "best case O(n)" if the best case is Theta(n), even though the algorithm may be quadratic on average.

You don't say the best case is O(n^2) if the best case is Theta(n log n) even though technically that would be correct.

Re: Big O Notation – Explained as easily as possible

#144

Post by blackbear_ »

chii wrote: post #142
codesparkle wrote: post #115

A bad programmer solves their problems inefficiently and a really bad programmer doesn't even know why their solution is inefficient To any beginners reading this: Solving problems inefficiently does not make you a bad programmer. Most of the time, an "inefficient" solution will be good enough, and optimising for performance comes at a cost. So sit back, relax, and enjoy the journey.

And great programmers would knowingly solve a problem inefficiently, because it's easier to write and ship it to the customer, and thus prove that the problem being solved is valuable.

Until, two years layer, the program needs one minute to start, every operation needs ten seconds to be executed and nobody knows why the program needs gigs of ram to stay idle and what to do about it.

Re: Big O Notation – Explained as easily as possible

#145

Post by gvx »

repsilat wrote: post #99
Al-Khwarizmi wrote: post #96

Earlier quoted context omitted.

I know the rest of the notations in the family but, to be honest, even in most algorithmics textbooks they tend to use Big O like 90% of the time, even in contexts where Big Theta would be more precise (e.g. "mergesort is O(n log n) in all cases"). Let alone in more informal contexts. I don't especially like it, but it's OK because it's not a lie. And I do think for people who just want the gist of the concept, like…

> even in contexts where Big Theta would be more precise (e.g. "mergesort is O(n log n) in all cases" Just to be careful here: the difference between big/little oh/theta/omega is orthogonal to best/worst/average case. A pedant could say that merge sort makes O(n^3) comparisons in both the best and worst case, ω(1) in both the best and worst case, etc. Colloquially, the former means "as fast as", and the latter means…

I've seen this a lot, where people are convinced big Oh is specifically meant for worst cases performance.

And there may be some logic behind it, because if some function is in Θ(n^3) in the worst case, then it is true that it is in O(n^3) in all cases, so maybe that is why they couple big Oh with worst case growth.

Re: Big O Notation – Explained as easily as possible

#146

Post by gvx »

volkk wrote: post #118
codesparkle wrote: post #115

A bad programmer solves their problems inefficiently and a really bad programmer doesn't even know why their solution is inefficient To any beginners reading this: Solving problems inefficiently does not make you a bad programmer. Most of the time, an "inefficient" solution will be good enough, and optimising for performance comes at a cost. So sit back, relax, and enjoy the journey.

Should also add that an inefficient solution for a mostly fixed input size is still going to be efficient. If you have to write a double for loop but the outer loop is iterating on a 1000 element array and the inner one is operating on a 26 element array (e.g alphabet), it's still a fast and probably good enough solution.

Operating on a fixed size datatype is trivially O(1), too (because O(c) = O(1) when c is a constant).

Re: Big O Notation – Explained as easily as possible

#147

Post by bnegreve »

maweki wrote: post #141
bnegreve wrote: post #136

Earlier quoted context omitted.

> 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…

> The steps are basic CPU operations such as load/store Only if you consider the result of a comparison as a "store" into the register. But again, comparing two objects might not be constant. The compiler I develop for my PhD, for example, uses (written in Haskell) somewhat nested sets and quite a few operations are dominated by the equality check. > It is only confusing when you confuse basic CPU operations with bas…

> But the author did exactly that, when they considered addition to be constant.

Ok, I agree the article is imprecise. It should say fixed width integer addition instead of simply addition since the latter can either refer to a simple ADD cpu instruction or to the much more complex '+' operator in python.

However, once you agree on this, the concept of step is clear enough: it is an ADD instruction (or LOAD+ADD+STORE if you wish, still constant time for fixed width types). Obviously, it does not mean that every occurrence of '+' in python can be computed in constant time.

Re: Big O Notation – Explained as easily as possible

#148

Post by d0mine »

crashocaster wrote: post #140
d0mine wrote: post #138

Earlier quoted context omitted.

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

that is obvious. But how does it change big O? (why any manual implementation would have a better big O compared to existing arithmetics implementation in CPython?)

Re: Big O Notation – Explained as easily as possible

#149

Post by maweki »

bnegreve wrote: post #147
maweki wrote: post #141

Earlier quoted context omitted.

> The steps are basic CPU operations such as load/store Only if you consider the result of a comparison as a "store" into the register. But again, comparing two objects might not be constant. The compiler I develop for my PhD, for example, uses (written in Haskell) somewhat nested sets and quite a few operations are dominated by the equality check. > It is only confusing when you confuse basic CPU operations with bas…

> But the author did exactly that, when they considered addition to be constant. Ok, I agree the article is imprecise. It should say fixed width integer addition instead of simply addition since the latter can either refer to a simple ADD cpu instruction or to the much more complex '+' operator in python. However, once you agree on this, the concept of step is clear enough: it is an ADD instruction (or LOAD+ADD+STORE…

This is exactly my point. In every somewhat lisp-like language, or even just considering operator overloading by any means (interfaces, for example), the concept of a step becomes unclear.

Say instead of the for-loop the author would use something like 'for idx in len(ls):' and then access items with [idx]. I think it's obvious that in order to know the runtime complexity, would would need to know what kind of access [] provides (linked list in linear time, array in constant time, treelist or skiplist in log time). That's why I said it's easy to hide behind implementation details. And if you do count them, with all intricacies, it gets quite complex.

We could now look at what the turing machine implementing that algorithm would do, as no "shortcuts" are allowed there. And the computational complexity is strongly bound to that kind of computation (Specifically it is unknown whether the number of derivation steps in lambda calculus translates to number of steps in a turing machine).

Re: Big O Notation – Explained as easily as possible

#150

Post by gvx »

aborsy wrote: post #89
pmiller2 wrote: post #86

Earlier quoted context omitted.

Sure it does, for all functions f and g that we actually care about in the CS context for big-O. Hint: what if f and g are smooth?

One function could be below another and have arbitrarily derivative. Even if they are both smooth: f(x)=sin(e^x) and g(x)=1.

Unless I'm mistaken, |g(x)|<M|f(x)| does not hold for those, since sin(e^x) has an infinite number of zeroes.
Post reply on HN