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 out of many members in a family of notations that has a very specific mathematical definition, other common ones being small-o and big-theta.
Analysis of algorithms is more difficult than it appears. 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, for example. In such case you could talk of big-omega (your analysis is bounded-below instead of bounded-above, asymptotically).
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 readers of this piece, it's enough and it's not worth being fussy about it.
What irks me is people who use the equal sign as in T(n)=O(n log n), though. Why would a function equal a class? Set membership notation does the job just fine.
> What irks me is people who use the equal sign as in T(n)=O(n log n), though. Why would a function equal a class? Set membership notation does the job just fine.
It's strange but it's fully standard. I would guess it develops from the use in analysis, where o(n) is more common. You derive your formula, it has a term in it that you don't want, you observe that "complicated term's numerator = o(n)", you take your limit, and the term vanishes away. Use of the = sign makes more sense there, because conceptually you're claiming something about the value of the term. (Specifically, that in the limit, it's equal to zero.)
> 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 "slower than".
I didn't really read that article as being for a developer. I read it and thought, hey, this one would be good to share with a few project managers & business unit managers. Any time people who are not programmers (especially ones we have to work with) start to better understand what we're really doing, it is a good thing. Articles like this are superb for helping them understand that developers do have a disciplined and rigorous way of solving problems.
I do agree with you that these articles do leave a lot of detail and precision out. They tend to give the reader a superficial understanding of the subject... but a superficial understanding may be enough to help.
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".
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 probably be read as "as n grows very large (whatever that means) the runtime approximates (whatever that means) some bound (below, above, whatever) f(n). yolo.".
But people should at least be _aware_ that they are being imprecise about it.
If I read a blog post or StackOverflow post or whatever and I see big-theta notation I know that the person is probably precise with her definition. If I see big-o then it may be correct, or accidentally correct (happens often due to the nature of the definition) or mistaken.
>Analysis of algorithms is more difficult than it appears. 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, for example. In such case you could talk of big-omega (your analysis is bounded-below instead of bounded-above, asymptotically).
Of course, that's why Big O says one thing, Compiler, CPU and Caches may say the other.
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.
>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 to explain their thought process is.
If someone is so pedantic that they would consider the interviewee to have shot themselves in the foot because they said "The big O is n squared." without any followup questions from the interviewer, that doesn't sound healthy to me. I would worry this kind of culture would extend past the interview and it wouldn't be an enjoyable place to work.
Can you imagine working in a place where people regularly argue over terminology instead of just making sure everyone is on the same page?
(Full warning: I'm not a dev, so I'm coming in from the view of another industry.)
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.
Last summer I was interviewing at a FAANG company for a supposed senior level position and I pointed this out.
Instead I was treated as if I fundamentally had no understanding of algorithms whatsoever. It was enormously frustrating, especially when I demonstrated real world runtime to the interviewer of two implementations.
If they need someone to actually make things work well on real physical hardware, they need to know how the claims map to the physical reality and the fundamental limitations of chalkboard optimization. The real world actually matters.
If he knew this maybe he wouldn't be overbudget, overdeadline and trying to mad hire people like some parody of the mythical man month...
8 months later it still rubs me the wrong way - that is, a bad faith read on new information as obviously objectively wrong and the speaker (me) as misinformed even after it's been demonstrated as accurate. Assuming everyone is stupid is a great way to hire, just fantastic.
I'd bet thousands the project is either still off the rails or they've overhauled the org chart.
The product hasn't been publicly announced yet btw.
It's really all for the best. This way I only wasted one day instead of say 6 additional months just spinning wheels against a stonewall.
> Instead I was treated as if I fundamentally had no understanding of algorithms whatsoever.
This and similar experiences, basically discovering the interviewer, potential boss, or worse, actual boss, is not a colleague but actually a shallow copy of what one would expect from someone in their role, is pretty common, especially (from what I've seen) in orgs with a clear divide between a "manager" class that is mostly composed of people with less experience than those they are managing, and those doing the work.
It's best, as you say, to just write off the time wasted on the discussion, move on, and be happy you don't have to work with them.
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.
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.
> 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 exaggeration? I’m inclined to accept another reason to dislike these super high level interpreted langs but I’ve never seen something that e.g. appears written to be logarithmic to become quadratic because of library implementation details.
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!).
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.
> 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?
I'm assuming you want something rigorous - based on the comment you replies to.
Many people will recommend CLRS [0] but I prefer it as a reference, rather than a learning resource. I feel it's very dry and academic.
Instead I'd recommend Tim Roughgarden's series of books Algorithms Illuminated for learning about analysis and algorithms. He also has courses on Coursera and Edx to cover the material. It's thorough rigorous and shows algorithms that apply to different paradigms - lke divide and conquer, graph theory.
Sedgewick and Wayne's Algorithms has a companion website with lots of additional material (heavily Java based) - and courses on Coursera too. Again I think it's more approachable than CLRS while still being detailed and covering the theory.
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.
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.
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!
I wanted to add something to this from recent personal experience.
I've worked with a few engineers recently who were keen - occasionally insistent - on coming up with an O(n log n) solution, or better, at design stages for a specific project. We were working on different parts of the platform (and in different dev environments) but essentially implementing the same thing.
For the implementation I tried to talk them into going with a simpler implementation that was O(n²) for the initial release, but they were adamant not to.
When it came to writing automated tests for the feature, I became aware of some edge cases that hadn't been considered during the design stages. We had another design meeting, updated the requirements, yadda yadda.
A day or so later I put the changes in for review and had them merged reasonably quickly. I later found out that the other group had to significantly rewrite their algorithm and write new tests from scratch, ultimately leading them to miss out on launching the feature at the same time as ours had been released.
The moral of the story? A good programmer knows _what_ the best algorithm is, but a good engineer knows _when_ a given algorithm is called for. Premature optimisation is, after all, the root of all evil.
I've since updated my version to coincide with their more performant version and rewritten a lot of my tests.
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.
Sometimes it is, a lot of the time it's not, or at least not so much so that you're a bad programmer if you do solve a problem but it's not as efficient as it could be. If there's one thing I've realized over a number of jobs where I tried to do things right, it's that most of the time all the work you do doesn't matter, won't last, and your bosses only care that they can list some feature on the product page. They define good programmer as someone who gets their tickets in on time, and if it matters, they can budget for you to improve it with another one.
It's also totally fine to waste some of your user's time if you first create value for them that they didn't have before. That's the nature of iteration and MVPs
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.
Good caveat; beginners should not bother about any of this stuff. Focus on good modularity, clear code structure and language idioms and in general for readability.
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 significant amount of mathematical background. But, that definition isn't that hard. It's simply:
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)| <= Mg(x).
And, if you're in an analysis of algorithms context, it's even easier, because you typically don't have to worry about this absolute value business.
Well, that M is essentially the reason you get to drop constant multiples of f(x). 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. (No need to prove this, because this is what makes the "less significant" terms less significant.)
I would also like to add that the equals sign in f(x) = O(g(x)) is one of the most useful abuses of notation that I know of, but it can be misleading. It doesn't behave at all like a real equality because it's not symmetric, but it is transitive and reflexive. It actually acts more like set membership than equality.
The short version is that the fastest-growing term dominates all the others and for large xs the smaller terms round down to zero. Since big-O notation is about how the complexity grows for large inputs, you can assume the input is arbitrarily large, and you'll notice that the complexity is completely determined by the fastest-growing term.
You drop the constant because it doesn't alter how the complexity grows as the input increases.
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 to assume for anyone who wants to be throwing around terms like "Big-O."
If it's not too intrusive, may I ask what your graduate degrees are?
A function f(n) is O(g(n)) if the graph of f will be underneath the graph of g(n) for a big enough n.
(If we want to be more correct, then I would have to add that if there exists a positive number c, and cg should be above the graph of f)
So f(n):=3n+28 will be O(n^2), because choosing c as 3, for every n greater than or equal 4, 3
n^2 will be greater than f(n).
It would help if I could draw some graphs, but hopefully it helps.
Had such students as well. If I ask anything they said, oh I learned that as undergrad (implying that it is too long ago to remember). I am sad about such a waste.
>> 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)| <= Mg(x).
is fairly similar to the so-called epsilon-delta definition of limits of functions. This way of reasoning is quite common. I know I bumped into it quite a lot: I learnt it in high school, even though I really understood it a couple of years later (I did a MSc in Physics). So the explanation above makes sense even if I never saw this exact formulation. Now I appreciate that not everyone is a Physics graduate, but I’d expect this to be understandable for people with degrees in applied Maths, Physics, or some related engineering discipline.
I'd say that the = is one of the most annoying abuses of notation that I know of, if not the most. Apart from not symmetric, which is a problem in its own right, for small o and small omega it's not even reflexive, which does not prevent the = users from using it also for those. Which amounts to using an equals sign to highlight how two functions differ.
And what do people gain with that? It's not as if a set membership symbol, which works just fine because big O, small o, the omegas and their ilk define sets of functions, doesn't work just fine and take the same space without being confusing.
The notation is from math; the point of it is that you can manipulate it like a normal expression, but it's "anonymous"; o(1) means some function that goes to zero, but we don't bother with a name, just recording the asymptotic behavior.
For example, f'(x) = lim (f(x+h)-f(x))/h can be rewritten with an error term f'(x) = (f(x+h)-f(x))/h + o(1), and then you can manipulate it more freely, say like f(x+h) = f(x) + hf'(x) + o(h). There's no need to drag out a bunch of useless names, each qualified by a set membership, to do this. I mean e(h) in o(1), e2(h) := h e(h) in o(h), etc.
The failure of "reflexivity", eg O(f) = O(f), is because the anonymity hides whether the two O(f)s are referring to the same function (ie. exactly what a name would tell us).
I understood your definition (all in all I had calculus 101) but to me it only describes why that is, it doesn't explain it.
Most Big-O explainers don't assume a mathematical background because to non-mathematicians parsing your definition feels like being told you're in a hot air balloon. They see the what, but they don't understand the why.
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 that for two constants 0 < c1 < c2 and large enough n, we have c1 < f(n)/g(n) < c2.
Finally, little o denotes vanishing behaviour. f(n) = o(g(n)) when f(n)/g(n) goes to 0 in the limit.
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”.
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/big-omega kind of way, because you want to just quickly have an idea of whether you'll write a really slow piece of code in general, not some best or worst case.
The question is simply what growth model dominates the increase of time/space for the algo for each of the inputs? Imagine the algo is already processing millions of input A, and you now increase A by a factor of 10, 100, etc.
This melts away all the setup costs, nothing machine specific like cache size matters, anything that isn't the dominating factor is swamped, and all you're left thinking about is probably how some loop expands. You also don't need to think about what coefficient that dominating term has, which you would if you tried to write an equation that took all the operations into account.
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)
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 language of the people that rule this industry and you either learn it or leave. That said, we can change it too, if we want.
>Big O notation can be quite informally understood by normal people.
Right; the concept is easily understood. It is the rigor of deriving and proving that is made difficult by the mathematicians which need not be that way.
As an example, Here is a neat communication from Faraday to Maxwell on receiving one of Maxwell's paper;
“Maxwell sent this paper to Faraday, who replied: "I was at first almost frightened when I saw so much mathematical force made to bear upon the subject, and then wondered to see that the subject stood it so well." Faraday to Maxwell, March 25, 1857. Campbell, Life, p. 200.
In a later letter, Faraday elaborated:
I hang on to your words because they are to me weighty.... There is one thing I would be glad to ask you. When a mathematician engaged in investigating physical actions and results has arrived at his conclusions, may they not be expressed in common language as fully, clearly, and definitely as in mathematical formulae? If so, would it not be a great boon to such as I to express them so? translating them out of their hieroglyphics ... I have always found that you could convey to me a perfectly clear idea of your conclusions ... neither above nor below the truth, and so clear in character that I can think and work from them. [Faraday to Maxwell, November 13, 1857. Life, p. 206]”
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 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.
Finally I'll say of all the obscure terminology for things intuitively applied, Big O has to be one of the most common, followed by gang of 4s design patterns.
> 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.
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 input terms as n, but also width of your terms (and python integers are arbitrary precision btw.).
So yeah, this is an upper bound on how many "steps" you do for every input, but often enough it's not really clear what a step is, especially if you have several "steps" that relate do different forms of data retrieval and organization (which often are culprits for bad performance if you're done optimizing the number of loops). Sometimes you can hide behind some guaruantees that your hashset has constant lookup. But did you factor in whether the hash function is actually constant (or even fast, for that matter)?
> 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)
> 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.
I learned a couple of things during a brief teaching stint. First, no matter how much math your students learned in their high school and college courses, you should expect to re-teach the concepts that are needed for your lesson. It needn't be extensive, but your students will thank you for it.
Second, don't introduce more than one hard concept at once. Asymptotes can be reviewed with pure math functions such as polynomials, but that's as far as they got in high school math. Then there are the other "interesting" orders such as log(n) that can be introduced, and you can show graphically why they're useful.
Now you're ready to discuss the order of algorithms.
I'm not a computer scientist, but that's how I learned it, and while I don't remember all of the algorithms today, I still understand the derivations of their orders when I see them.
Readit News
The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation, as Big O is just one out of many members in a family of notations that has a very specific mathematical definition, other common ones being small-o and big-theta.
Analysis of algorithms is more difficult than it appears. 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, for example. In such case you could talk of big-omega (your analysis is bounded-below instead of bounded-above, asymptotically).
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 readers of this piece, it's enough and it's not worth being fussy about it.
What irks me is people who use the equal sign as in T(n)=O(n log n), though. Why would a function equal a class? Set membership notation does the job just fine.
It's strange but it's fully standard. I would guess it develops from the use in analysis, where o(n) is more common. You derive your formula, it has a term in it that you don't want, you observe that "complicated term's numerator = o(n)", you take your limit, and the term vanishes away. Use of the = sign makes more sense there, because conceptually you're claiming something about the value of the term. (Specifically, that in the limit, it's equal to zero.)
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 "slower than".
I do agree with you that these articles do leave a lot of detail and precision out. They tend to give the reader a superficial understanding of the subject... but a superficial understanding may be enough to help.
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".
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 probably be read as "as n grows very large (whatever that means) the runtime approximates (whatever that means) some bound (below, above, whatever) f(n). yolo.".
But people should at least be _aware_ that they are being imprecise about it.
If I read a blog post or StackOverflow post or whatever and I see big-theta notation I know that the person is probably precise with her definition. If I see big-o then it may be correct, or accidentally correct (happens often due to the nature of the definition) or mistaken.
Most people who can program can grasp the informal meaning of O(n^2) pretty easily. They may not connect the word quadratic to that say concept.
Deleted Comment
Deleted Comment
Of course, that's why Big O says one thing, Compiler, CPU and Caches may say the other.
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.
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 to explain their thought process is.
If someone is so pedantic that they would consider the interviewee to have shot themselves in the foot because they said "The big O is n squared." without any followup questions from the interviewer, that doesn't sound healthy to me. I would worry this kind of culture would extend past the interview and it wouldn't be an enjoyable place to work.
Can you imagine working in a place where people regularly argue over terminology instead of just making sure everyone is on the same page?
(Full warning: I'm not a dev, so I'm coming in from the view of another industry.)
To some extent because the "that itself" is a deep field in its own right with its own specialized vocabulary.
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.
Instead I was treated as if I fundamentally had no understanding of algorithms whatsoever. It was enormously frustrating, especially when I demonstrated real world runtime to the interviewer of two implementations.
If they need someone to actually make things work well on real physical hardware, they need to know how the claims map to the physical reality and the fundamental limitations of chalkboard optimization. The real world actually matters.
If he knew this maybe he wouldn't be overbudget, overdeadline and trying to mad hire people like some parody of the mythical man month...
8 months later it still rubs me the wrong way - that is, a bad faith read on new information as obviously objectively wrong and the speaker (me) as misinformed even after it's been demonstrated as accurate. Assuming everyone is stupid is a great way to hire, just fantastic.
I'd bet thousands the project is either still off the rails or they've overhauled the org chart. The product hasn't been publicly announced yet btw.
It's really all for the best. This way I only wasted one day instead of say 6 additional months just spinning wheels against a stonewall.
We can argue about it being useful or not, but that don't change this fact.
This and similar experiences, basically discovering the interviewer, potential boss, or worse, actual boss, is not a colleague but actually a shallow copy of what one would expect from someone in their role, is pretty common, especially (from what I've seen) in orgs with a clear divide between a "manager" class that is mostly composed of people with less experience than those they are managing, and those doing the work.
It's best, as you say, to just write off the time wasted on the discussion, move on, and be happy you don't have to work with them.
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.
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 exaggeration? I’m inclined to accept another reason to dislike these super high level interpreted langs but I’ve never seen something that e.g. appears written to be logarithmic to become quadratic because of library implementation details.
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.
Node was actually very impressive, roughly as fast as D's reference compiler (cutting edge optimisations maybe 2 decades ago) in release mode.
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?
Many people will recommend CLRS [0] but I prefer it as a reference, rather than a learning resource. I feel it's very dry and academic.
Instead I'd recommend Tim Roughgarden's series of books Algorithms Illuminated for learning about analysis and algorithms. He also has courses on Coursera and Edx to cover the material. It's thorough rigorous and shows algorithms that apply to different paradigms - lke divide and conquer, graph theory.
Sedgewick and Wayne's Algorithms has a companion website with lots of additional material (heavily Java based) - and courses on Coursera too. Again I think it's more approachable than CLRS while still being detailed and covering the theory.
[1] https://mitpress.mit.edu/books/introduction-algorithms-third...
[2] http://timroughgarden.org/books.html
[3] https://algs4.cs.princeton.edu/home/
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.
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!
I've worked with a few engineers recently who were keen - occasionally insistent - on coming up with an O(n log n) solution, or better, at design stages for a specific project. We were working on different parts of the platform (and in different dev environments) but essentially implementing the same thing.
For the implementation I tried to talk them into going with a simpler implementation that was O(n²) for the initial release, but they were adamant not to.
When it came to writing automated tests for the feature, I became aware of some edge cases that hadn't been considered during the design stages. We had another design meeting, updated the requirements, yadda yadda.
A day or so later I put the changes in for review and had them merged reasonably quickly. I later found out that the other group had to significantly rewrite their algorithm and write new tests from scratch, ultimately leading them to miss out on launching the feature at the same time as ours had been released.
The moral of the story? A good programmer knows _what_ the best algorithm is, but a good engineer knows _when_ a given algorithm is called for. Premature optimisation is, after all, the root of all evil.
I've since updated my version to coincide with their more performant version and rewritten a lot of my tests.
It's also totally fine to waste some of your user's time if you first create value for them that they didn't have before. That's the nature of iteration and MVPs
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 significant amount of mathematical background. But, that definition isn't that hard. It's simply:
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)| <= Mg(x).
And, if you're in an analysis of algorithms context, it's even easier, because you typically don't have to worry about this absolute value business.
Well, that M is essentially the reason you get to drop constant multiples of f(x). 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. (No need to prove this, because this is what makes the "less significant" terms less significant.)
I would also like to add that the equals sign in f(x) = O(g(x)) is one of the most useful abuses of notation that I know of, but it can be misleading. It doesn't behave at all like a real equality because it's not symmetric, but it is transitive and reflexive. It actually acts more like set membership than equality.
"Hard" is relative to prerequisite knowledge, which can vary significantly.
You drop the constant because it doesn't alter how the complexity grows as the input increases.
If it's not too intrusive, may I ask what your graduate degrees are?
So f(n):=3n+28 will be O(n^2), because choosing c as 3, for every n greater than or equal 4, 3
n^2 will be greater than f(n).It would help if I could draw some graphs, but hopefully it helps.
>> 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)| <= Mg(x).
is fairly similar to the so-called epsilon-delta definition of limits of functions. This way of reasoning is quite common. I know I bumped into it quite a lot: I learnt it in high school, even though I really understood it a couple of years later (I did a MSc in Physics). So the explanation above makes sense even if I never saw this exact formulation. Now I appreciate that not everyone is a Physics graduate, but I’d expect this to be understandable for people with degrees in applied Maths, Physics, or some related engineering discipline.
And what do people gain with that? It's not as if a set membership symbol, which works just fine because big O, small o, the omegas and their ilk define sets of functions, doesn't work just fine and take the same space without being confusing.
For example, f'(x) = lim (f(x+h)-f(x))/h can be rewritten with an error term f'(x) = (f(x+h)-f(x))/h + o(1), and then you can manipulate it more freely, say like f(x+h) = f(x) + hf'(x) + o(h). There's no need to drag out a bunch of useless names, each qualified by a set membership, to do this. I mean e(h) in o(1), e2(h) := h e(h) in o(h), etc.
The failure of "reflexivity", eg O(f) = O(f), is because the anonymity hides whether the two O(f)s are referring to the same function (ie. exactly what a name would tell us).
Most Big-O explainers don't assume a mathematical background because to non-mathematicians parsing your definition feels like being told you're in a hot air balloon. They see the what, but they don't understand the why.
If g(x) dominates all the terms in f(x), then wouldn't lim_{x -> \infty} g(x)/f(x) go to infinity?
Correct.
Corollary: x is O(x^2), for example.
Using Omega instead denotes an asymptotic lower bound. To denote both, you use Theta: f(n) = Theta(g(n)) means that for two constants 0 < c1 < c2 and large enough n, we have c1 < f(n)/g(n) < c2.
Finally, little o denotes vanishing behaviour. f(n) = o(g(n)) when f(n)/g(n) goes to 0 in the limit.
I think of it pretty simply, but not in that formal big-theta/big-omega kind of way, because you want to just quickly have an idea of whether you'll write a really slow piece of code in general, not some best or worst case.
The question is simply what growth model dominates the increase of time/space for the algo for each of the inputs? Imagine the algo is already processing millions of input A, and you now increase A by a factor of 10, 100, etc.
This melts away all the setup costs, nothing machine specific like cache size matters, anything that isn't the dominating factor is swamped, and all you're left thinking about is probably how some loop expands. You also don't need to think about what coefficient that dominating term has, which you would if you tried to write an equation that took all the operations into account.
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)
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 language of the people that rule this industry and you either learn it or leave. That said, we can change it too, if we want.
Right; the concept is easily understood. It is the rigor of deriving and proving that is made difficult by the mathematicians which need not be that way.
As an example, Here is a neat communication from Faraday to Maxwell on receiving one of Maxwell's paper;
“Maxwell sent this paper to Faraday, who replied: "I was at first almost frightened when I saw so much mathematical force made to bear upon the subject, and then wondered to see that the subject stood it so well." Faraday to Maxwell, March 25, 1857. Campbell, Life, p. 200.
In a later letter, Faraday elaborated:
I hang on to your words because they are to me weighty.... There is one thing I would be glad to ask you. When a mathematician engaged in investigating physical actions and results has arrived at his conclusions, may they not be expressed in common language as fully, clearly, and definitely as in mathematical formulae? If so, would it not be a great boon to such as I to express them so? translating them out of their hieroglyphics ... I have always found that you could convey to me a perfectly clear idea of your conclusions ... neither above nor below the truth, and so clear in character that I can think and work from them. [Faraday to Maxwell, November 13, 1857. Life, p. 206]”
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 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.
Finally I'll say of all the obscure terminology for things intuitively applied, Big O has to be one of the most common, followed by gang of 4s design patterns.
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.
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 input terms as n, but also width of your terms (and python integers are arbitrary precision btw.).
So yeah, this is an upper bound on how many "steps" you do for every input, but often enough it's not really clear what a step is, especially if you have several "steps" that relate do different forms of data retrieval and organization (which often are culprits for bad performance if you're done optimizing the number of loops). Sometimes you can hide behind some guaruantees that your hashset has constant lookup. But did you factor in whether the hash function is actually constant (or even fast, for that matter)?
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)
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.
Second, don't introduce more than one hard concept at once. Asymptotes can be reviewed with pure math functions such as polynomials, but that's as far as they got in high school math. Then there are the other "interesting" orders such as log(n) that can be introduced, and you can show graphically why they're useful.
Now you're ready to discuss the order of algorithms.
I'm not a computer scientist, but that's how I learned it, and while I don't remember all of the algorithms today, I still understand the derivations of their orders when I see them.