A little bit of history: C++ programmers were always able to choose the right containers simply by using this image, since long before the invention of Big-O.

http://homepages.e3.net.nz/~djm/containerchoice.png

Can you explain how having a classification that allows one to determine whether something is logarithmic vs vs quadratic is so overrated?

Isn't that a bit like saying "Algebra is so overrated"?

Also Donald Knuth introduced Big O somewhere around the mid 1970s and C++ didn't come along until 1979.

https://en.wikipedia.org/wiki/Big_O_notation#cite_note-knuth...

Also your link is a visualization of ADTs not run times. And while it true that ADTs are chosen for certain guarantees it still depends on how they are used in an algorithm.

BTW, you are way off saying Don Knuth introduced Big O. It was invented by physicists and mathematicians like Paul Bachmann and Landau, many decades before the 1970s.

Sure "O" goes back to mathematicians in the late 19th century. What I meant was that Knuth introduced Big O(mnicron) in the context of "Computer Science" literature.

This is the source I am referring to from 1976 SIGACT News:

http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron...

On page 21 or page 4 of the PDF:

"I would like to close this letter by discussing a competing way to denote the order of function growth. My library research turned up the surprising fact that this alternative approach actually antedates the O-notation itself. "

On page 22 or page 5 of the PDF:

"The main reason why 0 is so handy is that we can use it right in the middle of formulas (and in the middle of English sentences and in tables which show the running times for a family of related algorithms etc.)."

Its use in computer science for algorithmic complexity came later. In fact, I believe in the early TAOCP, Donald did not use big O, but instead would derive the full expression where possible.

It boils down to optimization. There's no point in spending time optimizing for Big-O if the input size will be so small the difference between O(n²) and O(n log n) doesn't matter.

As with all optimizations, there are situations where it matters a lot. But in the real world there are plenty of situations where the time is better spent elsewhere or where there are other things that will necessitate replacing the code before the performance becomes a problem.

What about O(n!) and O(logn)?

I think that will probably explode even at microscopic input sizes.

Even in the real world, understanding what O is helps a lot. That doesn't mean you should use it everywhere or that you have to.

But it means you should understand how your code scales. Efficient code scales because it has a low order, inefficient code doesn't scale because it has a high order.

And if you replace the code, what have you done but change the order of the algorithm?

Computers are just a collection of functions with some order, some are O(n!), some O(1), some O(infinity) and some others are O(nlogn). Big-O is everywhere no matter if you admit it or not, so understanding it can be a big help to understand why Code A is faster or slower than Code B

Every optimization has a cost. Time is a finite resource. Time spent optimizing one thing could be spent optimizing something else or implementing a new feature or fixing a bug.

That said, the original argument isn't that that which Big-O notation represents is generally irrelevant. The argument is that the formalism of Big-O notation itself is generally irrelevant (except where it isn't, obviously).

You don't need CS101 to understand that a nested for-loop probably scales worse than a single if-statement. Or that looping over the input twice in succession is probably faster than nesting those loops. Or that only looking at half the input is faster than looking at all the inputs, and so on.

To put it in other words: you can figure out that something that scales from an ant to an elephant to a skyscraper scales worse than something that scales in multiples of ducks without having to use a ruler or charts. Big-O is the more accurate tool but there is a tremendous amount of situations where you don't need an accurate tool and a vague understanding of the same thing the tool would measure is entirely sufficient.

That sentence kinda defeats the argument itself. If it's irrelevant except where it is not, then your argument is obviously true.

We could also say that some number X is always not 1 except when it is.

>You don't need CS101 to understand that a nested for-loop probably scales worse than a single if-statement.

That is true, but it's just Big-O applied via intuition rather than learning.

Big-O is mostly the expression of intuition for some people.

"f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. "

If I were interviewing a candidate, and it was revealed he didn’t know Big-O notation, my next questions would be about data structures, because now I’m suspecting he wouldn’t even know how to implement the simplest of structures. What next, simple pointer arithmetic, is he unable to even walk an array?

We are no longer talking about a programmer then.

Not knowing these things, I usually chalk it up to either laziness, or lack of interest in understanding how things work.

Either way, that’s not someone I’d want on my team. Programmers should be enthusiastic about fundamentals. Good programmers have a “hacker” mentality, a need to know and understand inner workings, a craving to dig deep. I’d say this mentality is what you want from anyone in STEM.

You pointed out exactly how someone would not know -- they may have never taken computer science classes and taught themselves programming.

Or they may have taken some CS classes, not enough to have covered that particular concept.

I'd guess that, especially for older programmers, anecdotally, it's not uncommon to not really understand or use it.

I don't care if you're self-taught, it's audacious to even call yourself a programmer if you don't know the very basics of algorithms and data structures.

Just because someone doesn't use the same terminology to describe a set of concepts doesn't mean they don't understand those concepts.

Also, I wasn't aware there were were formal qualifications for someone adopting the title of "Programmer", pretty sure big-O notation isn't part of the dictionary definition.

The world of computers is full of things to learn about, more than almost any one person could learn in a lifetime.

People usually learn about what interests them, or what they need to know. It's entirely possible to be an accomplished programmer and never really learn big-O notation just as some programmers never learn assembly or C.

Think about it differently, big-O wasn't widely discussed or well known until the 1970s, thanks to Donald Knuth who popularized it. Then consider that many programmers who learned programming may have done so before it was widely known and some may have learned programming from those same people.

Are those programmers from roughly 1980 and earlier any less a programmer because they weren't aware of or didn't use big-O notation? Of course not.

Is big-O notation something most programmers should consider learning? Yes. But we should not seek to exclude others from a profession simply because they don't meet arbitrary criteria we think is necessary when they are clearly already actively engaged in that profession.

You're working in a field that requires you to use your brain, learn new stuff regularly, and solve problems. Isn't being ignorant of the fundamental concepts of your field a massive red flag that something is wrong?

If not, there are hundreds of other openings that the candidate can apply to.

Because pointer arithmetic is so vital to being a programmer in Python, Java, Ruby, JavaScript, ...?

Personally I know most of these things. I'm mostly self-taught. I looked into C++ at some point. I took some university courses. I've also been programming for a decade and a half (I'm 31, made my first website around age 10 and later picked up PHP before moving on to other languages).

But in my entire career there was not one point where I needed to implement a sorting algorithm myself. Or where I even had to know the difference between the various sorting algorithms. There have been a handful of situations where I needed to implement some kind of tree structure but very few moments where I benefited from knowing the difference between a list, an array, a stack or a queue (other than the different APIs in the standard libraries).

You are right that someone who's sufficiently interested in how things work will likely teach themselves these things even if they're not relevant to their work. But there's only so many hours in the day and not everyone shares the same interests. I have a basic understanding of several programming languages I don't use, including C/C++, C#, Prolog, Erlang and Haskell. I know many but not all of the concepts that make them different. I understand the general idea behind how assembler code works, formal logic, TCP vs UDP, endianness, binary representations of numbers, even some basic electrical engineering (I've played with Arduinos and shift registers). I also have a basic understanding of state machines, neural networks, genetic algorithms and all kinds of other stuff that will probably never be relevant for most of my work.

I'm a full-stack JavaScript developer these days so I also have some rudimentary knowledge of design and layout (color theory, spatial relations, typefaces, accessibility, etc) as well as database operations and Linux system administration. I know my limits -- I'm not a designer and I'm not a sysadmin and I feel more comfortable working together with them knowing they have my back.

I'm fully aware I have a broader knowledge when it comes to software development than most people I've had the fortune of working with. But I'm also fully aware that they often not only have deeper knowledge on any given subject than I might have but that no matter how broad my knowledge is it's incredibly likely that I have knowledge gaps in topics they might be taking for granted.

We like to stroke our ego and brag about the "hacker mentality" and how hackers are superior because we want to know everything (implying we can know everything or at least more than others). But knowledge isn't simply defined as a quantity. There are very few things that are essential knowledge to be a programmer and even they are debatable.

Calling people "not real programmers" is bullshit posturing. Software development is an incredibly broad field and no matter how good you are, you can never have expert knowledge of all of it (and even claiming a working knowledge in all of it strongly suggests your overall knowledge is so shallow as to be useless).

I've seen this kind of elitist bikeshedding over the definition of what is a "real programmer" since I wrote my first line of code. JavaScript is not a real programming language because you're "just scripting the browser". Shell programming is not real programming because it's just the interactive command line. Dynamically typed programming languages are not real programming languages because you can't write serious software in them. PHP programmers aren't real programmers because PHP is only used by amateurs. And on and on and on.

You know what? If I see someone applying for a programming job who doesn't know pointer arithmetic, I don't care. It's just pointer arithmetic. They can still learn that if they have to. Instead I focus on what they DO know. Maybe they come from a strong math and logic background and can optimize the crap out of our code. Maybe they come from a design background and can spot deep flaws in our fundamental assumptions. Maybe they have intricate domain knowledge and can us help make a product our users actually want.

Yes, if you apply to a senior C++ developer position and don't know pointer arithmetic or can't implement a linked list, you're probably not a good fit for the position. But flat out dismissals based on bullet points are bullshit.