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

71–80 of 168 posts

Re: Big O Notation – Explained as easily as possible

#71

Post by [deleted] »

tshaddox wrote: post #57
bjeds wrote: post #26

Earlier quoted context omitted.

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…

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

[deleted]

Re: Big O Notation – Explained as easily as possible

#72

Post by zachrose »

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…

I appreciate that the author was specific about “if you count addition as 1 operation.” Without saying this, it’s not obvious that the notation is such a simplified abstraction over operations and their costs, with all the limitations that come with that simplification.

Re: Big O Notation – Explained as easily as possible

#73

Post by bakuninsbart »

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…

Exactly, the link above starts well, but fails in some regards. If you use big O, you should give the mathematical definition and at least shortly explain it. The idea of an upper boundary isn't very hard, and it is actually important to understand that an algorithm running in O(n) is also running in O(n log(n)) is also running in O(n^2). It is at least necessary to understand the other greek letters, which really does come in handy in a deeper understanding of algorithms.

The list of "common" O's is also kinda bad. Particularly, and I see this all the time, I think it is a mistake to go from O(n^2) to O(c^n), as this is the step that leaves polynomial time complexity, and glosses over the fact, that each level of exponent constitutes a different time complexity. Here the mathematical notation of O(n^2), O(n^3), ..., O(n^l) is indispensible. Nesting loops is probably one of the most commonly relevant applications of O-notations, so this actually has an influence on real-world implementations.

Re: Big O Notation – Explained as easily as possible

#74

Post by Brian_K_White »

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?

Then just substitute whatever other operation that makes you happy? Or an imaginary one if you mean to say there is no such thing in real hardware.

Re: Big O Notation – Explained as easily as possible

#75

Post by melenaboija »

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…

I agree with what you say and not a Python fanatic but this high level language stigmas catch my attention.

If you try to implement your own, let's say, intersection of sets you will probably get at most the same performance as Python using a reasonable amount of time.

I guess my point is that seeing the comment of Python in a thread like this can also be confusing. Bad (or maybe I should say "not appropriate for your use") implementations can exist in any language.

Re: Big O Notation – Explained as easily as possible

#76

Post by aborsy »

pmiller2 wrote: post #39
mhh__ wrote: post #37

Earlier quoted context omitted.

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.

|g(x)|<M|f(x)| does not imply |g’(x)|<=C|f’(x)|.

Re: Big O Notation – Explained as easily as possible

#77

Post by cortesoft »

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…

I think the main purpose of an “explained as easily as possible” article is to help the reader understand when SOMEONE ELSE uses the term.

Sure, I can choose t use informal language, but I can’t stop someone else from using big o notation when speaking to me or writing something I want to read.

Re: Big O Notation – Explained as easily as possible

#78

Post by uh_uh »

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…

> And, you drop the least significant terms of f(x) because g(x) dominates them, i.e. lim_{x -> \infty} g(x)/f(x) = 0.

If g(x) dominates all the terms in f(x), then wouldn't lim_{x -> \infty} g(x)/f(x) go to infinity?

Re: Big O Notation – Explained as easily as possible

#79

Post by a1369209993 »

Brian_K_White wrote: post #66
sixstringtheory wrote: post #58

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 If a language/library can change the dominant asymptotic term of an algorithm like that, instead of just the constant factor, that is a problem. Does that really happen with python or is this e…

The language doesn't matter, nor even it's high vs low class. You can write a short function in any language that looks O(1) if you only look at the surface or high level of it. Even assembly. Meanwhile in the middle of that routine is a single call to another function or macro which may be 0(1) or O(n!). Python was just an example.

> Even assembly.

Although high-level languages like python or to a lesser but less excusable degree C++ are more susceptible to this because more features can secretly be greater-than-constant-time function calls.

Post reply on HN