You know, in years and years and years of programming, of applications and web and back-end and front-end etc etc, I have never had a real-life use case for Big-O notation, except in interviews. Nor had a real-life use case for caring about sort algorithms. I mean, not once.
I'd say the true foundation needed is entirely different. Avoiding spaghetti code, good refactoring practices, understanding when more architecture is needed, avoiding premature optimization or over-architecture, concepts like technical debt, writing code designed to be readable, how to establish practices and standards and make sure they're communicated properly... These are the kinds of things that actually matter in most projects.
(Obviously, if you're writing video codecs or kernel code, it's a whole different story...)
Okay, why do you use a hash table instead of a linked list when quick retrieval is more important than in-order traversals?
Now, it's pretty obvious when we're discussing something as simple as this, but this is the fundamental essence of Big O. Certainly, we don't need to calculate it on a daily basis, especially past the general case, but it also doesn't hurt to have common terminology when speaking about an edge case of an algorithm.
And just having a general feel of a graph of how quickly an O(n^2) algorithm can spiral out of control versus an O(log n) algorithm is useful. (That is, if you have a small amount of elements, it's not going to matter, but it will matter quickly as the number of elements grow.)
Eh, as a web programmer those certainly aren't a concern for me (and I hope this convo won't devolve into "web programmers aren't real programmers").
For both PHP and JS, there really isn't a difference; you're just given some basic data structures that handle pretty much everything under the sun, and you go from there. You can have an array with numeric keys (list), or you can have an array with string keys (dictionary), and it's only in your implementation that will determine if you use it as an iterative structure or as a kind of hash-lookup structure.
While PHP does have some advanced data structures provided by SPL, and some JS implementations offer typed arrays and such, they're rarely used in the wild for various reasons. I think the main reason, though, is probably that they're not really needed for 99.9% of web apps.
Well, I wouldn't phrase it that way, but it's not a fallacious argument.
If I were to rephrase, I would say, application developers aren't full stack developers.
Modern languages and frameworks hide a lot of complexity, allowing application developers to focus on business problems, which is a good thing.
But if you want to continue to grow as a programmer, and understand the tools you use, or use them to maximum efficiency, understanding things like Big-O analysis are crucial.
I don't often do complex "math" or analysis using Big-O... but understanding the core tenants are crucial, especially as you move from building apps to building frameworks themselves.
> you're just given some basic data structures that handle pretty much everything under the sun, and you go from there
This only works because the size of your n is small, possibly a few hundred, so it doesn't matter. When you start dealing with millions or billions of records this stuff matters. Quite a lot.
So really, it's not the language, it's the size of your data - or the size of n that matters.
Exactly, and how many web apps deal with millions of data points? Not many, as far as the view layer is concerned. Perhaps you'll have millions of rows in your DB, but you typically won't process all of those, at once, within PHP or JS. At least in my experience, most data processing on that scale happens in your OLAP layer (and thus is fully removed from the jurisdiction of PHP and JS).
Especially given single-page apps, you should never be dealing with millions of objects; with pagination and such, it's usually under a 1000 at a time, more typically 100 or so.
You're confusing wisdom and knowledge. Data structures and Big-O are mostly knowledge. It's stuff that can be transmitted from one person to another in form of cold, hard facts.
Avoiding spaghetti code, good refactoring practices, understanding when more architecture is needed -- all that stuff involves knowledge a lot less than wisdom. Sure, you can teach someone the basic principles, but until they've been bitten by some of the problems those principles try to solve, they won't truly know how to apply them.
The same can be said for algorithms and data structures: until you actually find yourself in a situation where you need finger trees because no other data structure fits your usage, you won't really know why finger trees are necessary and when to apply them. But the rules are a lot more clear-cut than when it comes to best practices.
Bottom line: both "computer sciencey stuff" (e.g. algorithms and data structures) and "best practices" (e.g. writing readable code and understanding when you need more architecture) can be learned and both require a degree of "wisdom" to apply, but the latter is a lot less clear-cut and has a lot more "maybes" in it.
Oh, and writing web stuff is not the only kind of work outside video codecs or kernel code. You could also be processing huge amounts of data, writing your own programming language or developing a game, for example.
The distinction between wisdom and knowledge is good. Personally, I don't even see the point of SW engineering in college; it's too much wisdom & experience based.
Also - I use the computer science conceptual framework every day. I lacked it - and badly - when I was a self-taught teenager soaking up as much online as I could.
I have never had a real-life use case for Big-O notation, except in interviews. Nor had a real-life use case for caring about sort algorithms. I mean, not once.
That is frightening. I can't think of any function I write without taking a second to think about what the Big-O would be.
And I don't even know how I could do things like parse input without knowing how to structure it so that look-ups never take more than log N time. And I don't know how I could do that without knowing sorting algorithms intimately.
And I am not writing codecs or kernel code, mostly it has been high performance and some soft real time, but I've also worked in back end web development.
Everything in your second paragraph I fully endorse, but your first paragraph is terrifying. I'm terrified I'll run into someone like you some day, clearly smart, clearly experienced and without a clue as to why I'm concerned about the Big-O of his implementation of something.
Some people know the computational complexity of something they write without knowing it in terms of Big O. Before my CS degree, I understood that looping through a list and for each item, looping through the same list again was not optimal. And someone only needs to write an O(n^3) algorithm once to realize that it's a very bad idea for any but the smallest amounts of data. Knowing about Big O is nice though, if only to understand documentation (realizing that O(nlogn) is better than O(n^2)).
I don't think he formally uses big-O but understands if something he is writing is linear (iterating over an array), exponential or O(1).
People have to get rid of their big hard on for Big-O, a useful concept that takes a couple hours to learn. It isn't a difficult thing that only the true macho programmers can know. I'd wish it was traditionally in starting programming books in the 'optimization & profiling' chapter and we wouldn't be having big fights about it.
>someone like you ... without a clue as to why I'm concerned about the Big-O
Except that's not what he said. He clearly does have a clue, he just hasn't actually needed it. And for application development, where most of the work is wiring together libraries, that's sounds about right.
Everyone writing code for a living has internalized when to use a map vs a vector. If that is the bar for "fundamental", then this whole discussion is pointless.
Just an anecdotal experience, but yes, I did happen to say things like "this lookup is O(n^2), you should use some other structure here". It's useful when that conversation ends with an "OK", rather than a wide eyes stare...
It just takes less time when you can explain something using common terms, rather than starting with what complexity is.
However most unreasonable cases are much less subtle than that - I run into "filter in the database, not in the app" more often than more complicated issues.
I completely agree. I very rarely catch myself saying "I wish the developer had understood the Big-O implications of this algorithm". I very often catch myself saying "I wish the developer would have realized that these 10 lines of code don't DO anything, and that this variable name is actively misleading." I find a very weak correlation between issues like the above and education levels. But maybe I'm biased. :)
Perhaps the reason you have never had to think about it is because you developed a good foundation for reasoning about algorithm time complexity?
I will say that I have never personally had to concern myself with a sorting algorithm (though I can definitely think of areas where one would), but pretty much everything else I have learned about algorithms has been extremely useful both as "tools for thinking about problems" and actually making correct and practical choices.
Sorting algorithms are taught because they are such a fundamental operation AND they provide some good "easy" examples for how different approaches can give you dramatically different performance. Some lessons can only be learned by actually seeing it for yourself.
I use the concept of Big-O notation, informally, almost every day. Almost every time I'm writing a new non-trivial method I ask myself, how will this scale to large values of n. Sure I don't sit down and formally prove anything and I rarely even spend a long time thinking about it. But knowing whether the function I'm about to write is O(n), O(n^2) or O(2^n) and understanding the implications of each is something I'd consider very fundamentally important.
I think this is just it though. You don't necessarily need to be able to sit down and formally write out the exact amortized big O complexity, (or little O, [O|o]mega or theta) but equally it's good to have some idea of how something would scale.
I feel like self taught developers who are serious just learn this by intuition because, frankly, if you're writing software where it matters then very quickly it becomes an obvious concern. If your self taught and it doesn't matter then it doesn't matter!
With a formal background you may or may not use it, but I'd say the only difference is knowing the formal notation makes talking about it with other programmers who also know that notation easier, but even then it's not like algorithmic complexity is (at it's heart) at particularly difficult concept when directly applied to a project. I always found it much harder as an abstract idea rather than when working with a specific algorithm.
You don't necessarily need to be able to sit down and formally write out the exact amortized big O complexity, (or little O, [O|o]mega or theta) but equally it's good to have some idea of how something would scale.
If you have a good idea of how things scale, being able to express exactly how they scale with succinct and clear notation is useful. Quite useful in fact.
That's why formal notation exists, because it is handy. Not because there is an eternal, global conspiracy among academics to keep up useless habits just to show off.
Big-O is a foundation for all of those things you mentioned as a true foundation. Don't know the former, you are likely to get tripped up by the later.
I get the feeling from your post that you get this though. Because at some point you have to transcend your knowledge of Big-O, pattern languages, and go through those stages of being an Architecture Astronaut, second-syndrome, failing, failing better, and then maybe even succeeding in what you do.
The 'foundation' as you use it changes greatly depending on what you use programs to do. If you are working on a user interface over a very simple problem, then design principles and maintanable code are critical.
If you are working on data analysis, than Big-O type basics become more important.
The point of having 'foundations', is that when you go to do almost a type of problem that you normally do not, such as CPU intensive data crunching, you know where to look for the information.
I have... a method using contains() on a list vs a HashSet(). In one instance the O(n) caused the method to run in 20-30 seconds. The O(1) ran in milliseconds. Just simple stuff like that can kill you if you don't have a basic foundation of knowledge.
When was the last time you counted over 1000 objects by hand? You were taught this skill because understanding how to count arbitrarily high ingrains certain concepts. Even if you don't count high every day, that understanding was the foundation of more interesting skills.
Comments
You know, in years and years and years of programming, of applications and web and back-end and front-end etc etc, I have never had a real-life use case for Big-O notation, except in interviews. Nor had a real-life use case for caring about sort algorithms. I mean, not once.
I'd say the true foundation needed is entirely different. Avoiding spaghetti code, good refactoring practices, understanding when more architecture is needed, avoiding premature optimization or over-architecture, concepts like technical debt, writing code designed to be readable, how to establish practices and standards and make sure they're communicated properly... These are the kinds of things that actually matter in most projects.
(Obviously, if you're writing video codecs or kernel code, it's a whole different story...)
Okay, why do you use a hash table instead of a linked list when quick retrieval is more important than in-order traversals?
Now, it's pretty obvious when we're discussing something as simple as this, but this is the fundamental essence of Big O. Certainly, we don't need to calculate it on a daily basis, especially past the general case, but it also doesn't hurt to have common terminology when speaking about an edge case of an algorithm.
And just having a general feel of a graph of how quickly an O(n^2) algorithm can spiral out of control versus an O(log n) algorithm is useful. (That is, if you have a small amount of elements, it's not going to matter, but it will matter quickly as the number of elements grow.)
Eh, as a web programmer those certainly aren't a concern for me (and I hope this convo won't devolve into "web programmers aren't real programmers").
For both PHP and JS, there really isn't a difference; you're just given some basic data structures that handle pretty much everything under the sun, and you go from there. You can have an array with numeric keys (list), or you can have an array with string keys (dictionary), and it's only in your implementation that will determine if you use it as an iterative structure or as a kind of hash-lookup structure.
While PHP does have some advanced data structures provided by SPL, and some JS implementations offer typed arrays and such, they're rarely used in the wild for various reasons. I think the main reason, though, is probably that they're not really needed for 99.9% of web apps.
Well, I wouldn't phrase it that way, but it's not a fallacious argument.
If I were to rephrase, I would say, application developers aren't full stack developers.
Modern languages and frameworks hide a lot of complexity, allowing application developers to focus on business problems, which is a good thing.
But if you want to continue to grow as a programmer, and understand the tools you use, or use them to maximum efficiency, understanding things like Big-O analysis are crucial.
I don't often do complex "math" or analysis using Big-O... but understanding the core tenants are crucial, especially as you move from building apps to building frameworks themselves.
> you're just given some basic data structures that handle pretty much everything under the sun, and you go from there
This only works because the size of your n is small, possibly a few hundred, so it doesn't matter. When you start dealing with millions or billions of records this stuff matters. Quite a lot.
So really, it's not the language, it's the size of your data - or the size of n that matters.
Exactly, and how many web apps deal with millions of data points? Not many, as far as the view layer is concerned. Perhaps you'll have millions of rows in your DB, but you typically won't process all of those, at once, within PHP or JS. At least in my experience, most data processing on that scale happens in your OLAP layer (and thus is fully removed from the jurisdiction of PHP and JS).
Especially given single-page apps, you should never be dealing with millions of objects; with pagination and such, it's usually under a 1000 at a time, more typically 100 or so.
You're confusing wisdom and knowledge. Data structures and Big-O are mostly knowledge. It's stuff that can be transmitted from one person to another in form of cold, hard facts.
Avoiding spaghetti code, good refactoring practices, understanding when more architecture is needed -- all that stuff involves knowledge a lot less than wisdom. Sure, you can teach someone the basic principles, but until they've been bitten by some of the problems those principles try to solve, they won't truly know how to apply them.
The same can be said for algorithms and data structures: until you actually find yourself in a situation where you need finger trees because no other data structure fits your usage, you won't really know why finger trees are necessary and when to apply them. But the rules are a lot more clear-cut than when it comes to best practices.
Bottom line: both "computer sciencey stuff" (e.g. algorithms and data structures) and "best practices" (e.g. writing readable code and understanding when you need more architecture) can be learned and both require a degree of "wisdom" to apply, but the latter is a lot less clear-cut and has a lot more "maybes" in it.
Oh, and writing web stuff is not the only kind of work outside video codecs or kernel code. You could also be processing huge amounts of data, writing your own programming language or developing a game, for example.
The distinction between wisdom and knowledge is good. Personally, I don't even see the point of SW engineering in college; it's too much wisdom & experience based.
Also - I use the computer science conceptual framework every day. I lacked it - and badly - when I was a self-taught teenager soaking up as much online as I could.
I have never had a real-life use case for Big-O notation, except in interviews. Nor had a real-life use case for caring about sort algorithms. I mean, not once.
That is frightening. I can't think of any function I write without taking a second to think about what the Big-O would be.
And I don't even know how I could do things like parse input without knowing how to structure it so that look-ups never take more than log N time. And I don't know how I could do that without knowing sorting algorithms intimately.
And I am not writing codecs or kernel code, mostly it has been high performance and some soft real time, but I've also worked in back end web development.
Everything in your second paragraph I fully endorse, but your first paragraph is terrifying. I'm terrified I'll run into someone like you some day, clearly smart, clearly experienced and without a clue as to why I'm concerned about the Big-O of his implementation of something.
Some people know the computational complexity of something they write without knowing it in terms of Big O. Before my CS degree, I understood that looping through a list and for each item, looping through the same list again was not optimal. And someone only needs to write an O(n^3) algorithm once to realize that it's a very bad idea for any but the smallest amounts of data. Knowing about Big O is nice though, if only to understand documentation (realizing that O(nlogn) is better than O(n^2)).
I don't think he formally uses big-O but understands if something he is writing is linear (iterating over an array), exponential or O(1).
People have to get rid of their big hard on for Big-O, a useful concept that takes a couple hours to learn. It isn't a difficult thing that only the true macho programmers can know. I'd wish it was traditionally in starting programming books in the 'optimization & profiling' chapter and we wouldn't be having big fights about it.
>someone like you ... without a clue as to why I'm concerned about the Big-O
Except that's not what he said. He clearly does have a clue, he just hasn't actually needed it. And for application development, where most of the work is wiring together libraries, that's sounds about right.
Everyone writing code for a living has internalized when to use a map vs a vector. If that is the bar for "fundamental", then this whole discussion is pointless.
Just an anecdotal experience, but yes, I did happen to say things like "this lookup is O(n^2), you should use some other structure here". It's useful when that conversation ends with an "OK", rather than a wide eyes stare...
It just takes less time when you can explain something using common terms, rather than starting with what complexity is.
However most unreasonable cases are much less subtle than that - I run into "filter in the database, not in the app" more often than more complicated issues.
I completely agree. I very rarely catch myself saying "I wish the developer had understood the Big-O implications of this algorithm". I very often catch myself saying "I wish the developer would have realized that these 10 lines of code don't DO anything, and that this variable name is actively misleading." I find a very weak correlation between issues like the above and education levels. But maybe I'm biased. :)
Perhaps the reason you have never had to think about it is because you developed a good foundation for reasoning about algorithm time complexity?
I will say that I have never personally had to concern myself with a sorting algorithm (though I can definitely think of areas where one would), but pretty much everything else I have learned about algorithms has been extremely useful both as "tools for thinking about problems" and actually making correct and practical choices.
Sorting algorithms are taught because they are such a fundamental operation AND they provide some good "easy" examples for how different approaches can give you dramatically different performance. Some lessons can only be learned by actually seeing it for yourself.
I use the concept of Big-O notation, informally, almost every day. Almost every time I'm writing a new non-trivial method I ask myself, how will this scale to large values of n. Sure I don't sit down and formally prove anything and I rarely even spend a long time thinking about it. But knowing whether the function I'm about to write is O(n), O(n^2) or O(2^n) and understanding the implications of each is something I'd consider very fundamentally important.
I think this is just it though. You don't necessarily need to be able to sit down and formally write out the exact amortized big O complexity, (or little O, [O|o]mega or theta) but equally it's good to have some idea of how something would scale.
I feel like self taught developers who are serious just learn this by intuition because, frankly, if you're writing software where it matters then very quickly it becomes an obvious concern. If your self taught and it doesn't matter then it doesn't matter!
With a formal background you may or may not use it, but I'd say the only difference is knowing the formal notation makes talking about it with other programmers who also know that notation easier, but even then it's not like algorithmic complexity is (at it's heart) at particularly difficult concept when directly applied to a project. I always found it much harder as an abstract idea rather than when working with a specific algorithm.
You don't necessarily need to be able to sit down and formally write out the exact amortized big O complexity, (or little O, [O|o]mega or theta) but equally it's good to have some idea of how something would scale.
If you have a good idea of how things scale, being able to express exactly how they scale with succinct and clear notation is useful. Quite useful in fact.
That's why formal notation exists, because it is handy. Not because there is an eternal, global conspiracy among academics to keep up useless habits just to show off.
Big-O is a foundation for all of those things you mentioned as a true foundation. Don't know the former, you are likely to get tripped up by the later.
I get the feeling from your post that you get this though. Because at some point you have to transcend your knowledge of Big-O, pattern languages, and go through those stages of being an Architecture Astronaut, second-syndrome, failing, failing better, and then maybe even succeeding in what you do.
Then things begin to get interesting.
The 'foundation' as you use it changes greatly depending on what you use programs to do. If you are working on a user interface over a very simple problem, then design principles and maintanable code are critical.
If you are working on data analysis, than Big-O type basics become more important.
The point of having 'foundations', is that when you go to do almost a type of problem that you normally do not, such as CPU intensive data crunching, you know where to look for the information.
I have... a method using contains() on a list vs a HashSet(). In one instance the O(n) caused the method to run in 20-30 seconds. The O(1) ran in milliseconds. Just simple stuff like that can kill you if you don't have a basic foundation of knowledge.
Uh, if you know when to use rb-trees, hash tables or arrays, you are using big-O.
When was the last time you counted over 1000 objects by hand? You were taught this skill because understanding how to count arbitrarily high ingrains certain concepts. Even if you don't count high every day, that understanding was the foundation of more interesting skills.