I think so. I reckon if I asked any of the developers I work with "what is Big O" I wouldn't expect any of them to know, but maybe I would be pleasantly surprised. No, no I wouldn't. I have seen their code, they definitely don't know what Big O is.
Whenever I interview I'm always asked the usual leetcode bullshit. Are there programming jobs that don't ask/require this stuff?
I have met a lot of analysts and researchers that code Python for data science that know nothing of big O, but that's to be expected.
I've had to explain what hash maps are.
I've had to explain why nested foreach loops are bad.
I've seen code where the dev wanted to create a collection of Foo, they didn't know how many Foos would be in the collection so they made an array that was far bigger than they needed. They then added all the items to the Array one by one, then performed a loop which went round the Array starting at the end and on each iteration it would check if the last item was null. They then resized the Array by 1 item to remove the null entry.... The loop did this until it hit an item that wasn't null...
This in a language that has List<T> type...
They at least had the sense to write a comment saying someone needed to look into this as it was slow for some reason...
This wasn't a junior developer either, it was someone with 15+ years experience. This person would have no idea what Big O meant.
I've seen nested foreach loops with a database call in the inner loop!
1) Not knowing
2) Knowing Big O and thinking it is always important
3) Knowing Big O and realizing constants matter in practice so you stop optimizing prematurely
Anyway, that was my evolution. I agree with most of what you say except I think I would change complex algorithm to complex data structure.
For example, with Scala simple Arrays outperform most other collections, including Vectors and Lists, even when the big O is bad.
Array languages are especially powerful, even though algorithms implemented in them often do a lot of extra work. If you can keep all of your data in L1, it doesn't much matter what big O you have (usually) and the most naive data structures and algorithms will usually outperform fancy pointer chasing stuff in L3 or RAM.
4) Realizing that there is a Big O around the larger architecture and thinking it is always important
5) Realizing that archecture is determined by the problem space, so addressing the problem itself as directly as possible will converge on optimal Big O
Once you've done it over and over for years it becomes more clear how Big O just reflects the assumptions, and fighting it at the terminating point of the specific algorithms and data is a thing to defer until an easy win is needed. The only effort greenfield code deserves for optimization, OTOH, is to quickly review the language's built-in structures, and pick the one that is approximately best. Push the features, then as time permits build profiling mechanisms to find the hotspots as the system gets production data.
6) Realizing that Big O doesn't matter when you can guarantee your data is always small.
Maybe this is more like 4.1 or 5.1, but it certainly does come up.
Even if they went to a good university, they might have sleep-walked through their calc/analysis courses and then encountered this stuff later in upper level CS, and learned by rote just enough to pass the class.
It's because of a lack of focus on fundamentals in undergrad education.
> ...sleep-walked through their calc/analysis courses...
I think you both identified the problem and shot down your argument in one breath here. Self taught developers can probably be forgiven for not knowing what big O is, right up until the point where someone asks them about it, and they say "what's big O?" After that, nothing prevents anybody from cracking a book or going on the internet to figure it out.
People who don't realize this end up here: https://accidentallyquadratic.tumblr.com/ :)
And it is often worth realizing that often you can shave time for space, but the setup costs aren't zero. Nor do you always have the space to setup. (For fun in this vein, lookup sortation networks.)
As soon as you start utilizing a data structure or calling another function, understanding the asymptotic behavior of each call can be super helpful. For example:
public void f(List a, List b) {
for(Object o : a) {
if(b.contains(a)) {
b.remove(a);
}
}
}
Big O can also be misleading; modern computers may execute some optimal algorithm slower than a less optimal one, because of cache performance or whatever.
We need to make a bigger fuss out of the "C" in Big O, teach people how to use a profiler, and teach more about memory layout and how computers actually function - time complexity isn't time of execution. But too many people treat it like that.