I was under the impression that the concepts of time and memory complexity are a must for graduates of compsci courses, but having studied engineering I have no knowledge if that is the case. I have recently been surprised to interview some graduates of a local college that do not even know the concept. I guess my question is:
Is the concept of computational complexity important for software developers? And should it be taught in undergraduate courses?
In most universities, I assume (I hope!) that time and memory complexity is definitely part of their courses.
Now, these "complexities" are a very elastic topic. Whether people should really know all the theory like "ZPP is the complexity class of decision problems that can be solved with zero error on a probabilistic Turing machine in polynomial time." and such kind of stuff is questionable. I personally consider these advanced theories irrelevant to software development.
On the opposite, I consider that every developer should be aware of the time/space complexity of the data structures and algorithms they use.
Many beginners suffer from micro-optimization obsession. Learning comp. complexity steers students towards a much more practical way of estimating performance and scalability, in my experience.
From what I've seen, it seems that big-O notation and time and memory complexity are emphasized a lot in formal computer science education... however being self-taught, this perception is based on hearing and reading what people with such educations say and write.
Though I do believe the general ideas and concepts are important, I don't believe the formalization of it (such as big-O notation and various terminology) matters nearly as much, except for the purposes of communication. Just because someone isn't familiar with the formal notation and terminology doesn't mean they can't see how and why one algorithm would be faster than another in a particular case. People can see that the time taken to search a balanced binary tree relates to the base-2 logarithm of the number of nodes without first learning about complexity theory in any formal sense, if they understand how the tree works and have a reasonable grasp of high school math. It's important to know when to pay attention to complexity and memory use, and to consider typical and worst cases, though... but some people don't. Of course, a formal background in the theory might help, but not having it doesn't mean one can't apply the concepts.
The notation and terminology become important for communication. They give a nice way to convey a quantification of the performance of an algorithm to someone else. Because it comes up in papers and explanations frequently, it's useful to have at least a vague understanding of it so that they're easier to follow.
So yes, the concepts are important (though less so when resources and time are ample but data isn't). But though the concepts are important, the formalization of them is often not so important -- and one needs to remember that the notation and terminology are not the same as the concepts themselves.
Edit:
I wouldn't claim to understand the concepts in as much detail as someone who's formally studied, but a lot of the general ideas just make sense. I do think there's value in formally studying this, but some of that value can still exist without.
As for introducing the concepts (outside formal study), I think a good start is to encourage people to think about how much memory overhead the data structures have, what steps the algorithms involve, and how these things change with different data.
It also helps to consider hypothetical situations and changes, like considering what happens if a tree is balanced versus what happens if it's as unbalanced as possible, or how many levels into the tree most of the nodes would be, or how many more nodes it can hold if the depth is increased one level. This way of thinking is generally useful for programmers anyway, not just when looking at complexity; and if applied to thinking about how algorithms and data structures perform under different circumstances it naturally points in the same direction as a more formal examination of complexity would.
Yes
Understanding the basics of complexity is important and should be something that you learn as an undergrad. In fact I think it is usually touched on in whichever class teaches you about data structures. I can understand graduates not understanding or not remembering, but I can't see them not having been taught the basics of complexity.
Update: Why is it Important
I was on a database migration at a particular job. We had a deadline for when the migration needed to get done. The person who wrote the script didn't have any grounding in complexity. Unfortunately, nobody else looked closely at the logic he used in in the script. I don't remember the specifics other than he used a doubly nested loop instead of a hashtable. After a week of the script running continuously we took at the look of the logic, realized the problem. It took something like 5 hours to complete after the change. We almost missed the deadline for migration completion as a result of someone not understanding complexity.
The point is it's easy to accidentally make something that is orders of magnitude slower, or will always run out of memory before the job completes. While faster machines with more memory can mitigate small mistakes, they often cannot mitigate complexity issues.
I find that asking whether it's "important or not" is rather vague.
You'll find many people evangelizing on how every smallest bit of knowledge in this world is strictly required in their opinion. But that's a bit pointless, because one can never know everything, and one should not be expected to unless it helps one to meet the requirements his job poses. I prefer to take a more pragmatic approach to educational prerequisites, in general, unless it's a matter of hobby or arbitrary personal preference.
Is it important for programmers that are expected to write extremely efficient code or innovative infrastructural algorithms? Yes.
Is it important for programmers who develop conventional web applications? They can manage without it or get efficient implementations in the open source world.
Is it important for programmers who develop GUIs for applications? Probably not, because successful GUI frameworks abstract all those small details away.
It's always nice to know, just like anything, but it doesn't keep many (or even most) programmers from simply doing their job to the satisfaction of their employers.
On the other hand, if one signed up for higher studies, in search of fundamental and theoretical education, one should be expected to learn subjects that are by definition more theoretical than practical. In my opinion, it is essential that CompSci. students learn about complexity, just as it's important they learn about calculus.
But anyway, since when do CompSci. programs teach people how to be good programmers? For that you have specialized training programs and practical experience (either yours or your fellow programmers who can share theirs with you).
