Big O Notation – Explained as easily as possible • Hacker News Board

Re: Big O Notation – Explained as easily as possible

#151

Post by Al-Khwarizmi » Sun, Jan 17, 2021, 11:14 AM UTC

gvx wrote: post #145

repsilat wrote: post #99

Earlier quoted context omitted.

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

Again, I think from a shallow perspective it makes sense.

If an algorithm always runs in O(n^3), then it's guaranteed that it runs in O(n^3) in the worst case. And if an algorithm runs in O(n^3) in the worst case, then it's guaranteed to always run in O(n^3) (but not in Θ(n^3), of course). So if you only care about worst-case performance, it's reasonable to only use the big O.

Of course, what your parent comment says is also true - you could say that mergesort is O(2^n), in the worst case or in any other case, and be correct because it's an upper bound. But people using Big Oh informally don't say that because you typically want to show how good your algorithm is, so you use the tightest upper bound possible (i.e. the big theta of the worst case).

Re: Big O Notation – Explained as easily as possible

#152

Post by gvx » Sun, Jan 17, 2021, 11:52 AM UTC

dfdz wrote: post #130

Disclaimer: I am very familiar with big O notation and find it intuitive. However, I think the notation \lesssim or f(n) \lesssim g(n) if there is an absolute constant C such that f(n) \le C g(n) the meaning is completely clear and by rearranging an expression it can replace big O notation. For example instead of writing f(n) = g(n) + O(h(n)) you write |f(n) - g(n)| \lesssim h(n) https://math.stackexchange.com/questi…

If I understand correctly, f(n) << g(n) is equivalent to f(n) = o(g(n)), not f(n) = O(g(n)).

Re: Big O Notation – Explained as easily as possible

#153

Post by kodah » Sun, Jan 17, 2021, 1:35 PM UTC

asperous wrote: post #112

kodah wrote: post #105

I learned to code as a kid and only met mathematicians who consider themselves programmers as an adult. Some opinion, maybe unpopular: Big O notation can be quite informally understood by normal people. It is academic people that make it and keep it challenging because it is how they understand the world. This is why interviews have stayed materially gruesome despite loud voices wishing it weren't so. It's the langua…

I have met a lot of programmers that don't know about the concept nor do they proactively think to apply it. I do understand the disconnect between knowing snobby language and doing good work. Certainly you can be an amazing programmer and apply these ideas possibly without ever even being trained on them or knowing the jargon. In industry at least, a lot of work is communication so you have to know what things are c…

> In industry at least, a lot of work is communication so you have to know what things are commonly called to explain your thoughts to other people. and along those lines Mathematicians are the ones that are studying this concept in the abstract, so its useful to use their lingo because then you know where to find all the abstract knowledge on the subject.

I think this is what I'm getting at. Mathematicians can adjust their language to communicate with a wider audience, especially on things as so commonly understood as Big O. It's a two way street, because you need to know and understand mathematical principles to be a good programmer, but if this is your only mode of understanding you are equally useless. There needs to be hiring gates for both.

Re: Big O Notation – Explained as easily as possible

#154

Post by otabdeveloper4 » Sun, Jan 17, 2021, 1:49 PM UTC

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…

> f(x) is O(g(x)) iff there exists a positive number M and an x_0 such that for all x > x_0, |f(x)| Correct.

Corollary: x is O(x^2), for example.

Re: Big O Notation – Explained as easily as possible

#155

Post by deburo » Sun, Jan 17, 2021, 3:26 PM UTC

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.

That's a popular sentiment to always cuddle new players in a field, but knowing the performance of your algos is part of the job. Performance comes into play in many scenarios. Your users may not "care", but you might be wasting a lot of their time.

Re: Big O Notation – Explained as easily as possible

#156

Post by rytill » Sun, Jan 17, 2021, 3:27 PM UTC

adamnemecek wrote: post #102

amelius wrote: post #91

Earlier quoted context omitted.

On constant-size hardware? And doesn't getting the data in and out already take O(N)?

Are you talking about arbitrary sized or infinite sized?

We’re saying the time, space, or some other metric of the solution scales with the size of the input number in a way that is not constant. The number could be any input (arbitrary).

Re: Big O Notation – Explained as easily as possible

#157

Post by kaba0 » Sun, Jan 17, 2021, 3:40 PM UTC

d0mine wrote: post #148

crashocaster wrote: post #140

Earlier quoted context omitted.

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

I think he meant that naively implementing an algorithm may not be bounded by the O notation he/she originally wanted due to code calling other functions “hidden” from the programmer.

Re: Big O Notation – Explained as easily as possible

#158

Post by kaba0 » Sun, Jan 17, 2021, 3:49 PM UTC

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.

Inefficiency and algorithmic complexity is imo not necessarily the same all the time.

For a beginner, inefficiencies like allocating in loops and the like (which can often be optimized) are not that big of a problem, since they only change a constant factor. On the other hand, O(n^2) and it’s supersets can be problematic when applied blindly. I don’t remember the exact situation but I recall a GUI app that listed some options in a drop-down menu. But on each click, they managed to call a function with O(n^2) complexity and you don’t need many elements to get a big number that way, so the drop-down visibly froze the UI (I guess it was an older framework with no separate thread/just bad code that worked on the main thread).

Of cource relax and enjoy programming, but I think reading up on algorithms can be fun and useful for the long term!

Re: Big O Notation – Explained as easily as possible

#159

Post by kaba0 » Sun, Jan 17, 2021, 3:54 PM UTC

tromp wrote: post #59

Note that f(n) = O(g(n)) denotes an asymptotic upper bound. So it would be correct (if confusing) to say that 2n+3 = O(n^2). This is important for use in algorithmic complexity because we may not always be able to determine the running time even up to a constant, but can more easily infer an upper bound. Using Omega instead denotes an asymptotic lower bound. To denote both, you use Theta: f(n) = Theta(g(n)) means tha…

A nitpick because this is an accepted notation, but as others mentioned in the thread: when someone writes 2n+3 = O(n) they mean 2n+3 \in O(n) (\in is little epsilon in latex, that is “element of set”), since O(f) is the set of all functions that has “f as an upper bound”.

Re: Big O Notation – Explained as easily as possible

#160

Post by kaba0 » Sun, Jan 17, 2021, 4:04 PM UTC

lordnacho wrote: post #60

The thing that didn't click for me was precisely the "try to count the operations" thing that the author mentions. In fact it's the wrong road to go down, it isn't the point of big-o, and yet that's how you're invited to think about it when the issue is presented in college. It's only natural to think "oh let's look at all the operations and add them up". I think of it pretty simply, but not in that formal big-theta/…

It was the contrary for me. I think it helps understanding that we are actually put a value to each line of code that gets executed, but instead of microbenchmarking, we do it in an abstract way, say print gets c1 constant, addition gets c2 and the like. For loops will multiply the instructions’ sum inside them by the number of times they get executed. And basically that’s it. You sum the whole thing and get something like (c1+c2)n+c3 for a for loop over an n element list or something with two instructions inside and one other outside the loop. Since these were arbitrary constants, c1 and c2 can be replaced by another one, so you’ve got cn+c3, and since (I’m not gonna be mathematically rigorous here) as n changes, it will be much larger than the others, we are only interested in it, hence it was an O(n) algorithm.

The eye-opening thing about it was that for simple algorithms, I only need high-school math to analyze them for different measurements. Like, memory allocation is costly for this sort of application and I want to measure that, just count each malloc instead! (But do note that it is quite hard/impossible to rigorously analyze programs for modern CPUs with cache misses and the like)