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".
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.
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).
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.
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.
/* This is O(scary), but seems quick enough in practice. */
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.
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 project required high performance, high throughout, distributed computing with exabytes of data.
The person applying for the job should illustrate they can deal with that and knows when to ask what kind of question.
If they think chalkboard algo analysis is the end of the game, that they can just pack up and go home, not looking at the actual hardware specifications and capabilities, the real world implementations and costs, and just blindly trust the mathematical abstraction without any type of evidence, analysis, testing, or considerations of a system as complex as the physical hardware they are using, then good luck.
For example, if there is a "slower" implementation that's embarrassingly parallelizable and trivial to distribute, those are actually important factors.
If they have a "slower" implementation that also allows for a quicker mark and sweep or cache invalidation, those are also actually important.
If input data can be tightly characterized, that's actually important, it changes the real world expected results.
Bursty and continuous traffic are different problems so average throughput is insufficient for characterization.
This guy disputed all that. Basically the midterm I took 20 years ago as an undergrad when I 18 at the University, that's it. That's all of HPC.
By the end I was just giving him the college freshman level answers and he was genuinely surprised as if he thought I didn't know it.
Again, last I heard, the project is still on the rocks.
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.
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.
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...
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).