Accidental vs Essential Complexity

If you have not heard of this before here is a neat way to look at it....

say that you want to find the biggest number in an array. To do that first you decide to sort the array and then do the finding. Assuming the running time of the algorithm is your complexity your algorithm has O(n^2) complexity. Then some one comes up and say I can do it in O(nlogn) time. Well , in that case you have introduced some complexity in to your algorithm than this one and hence that's an accidental complexity. After thinking for while you decide..Wait a minute I can do it in O(n) time by simply comparing each number and remembering the highest! So now the nlogn becomes an accidental complexity. Now if someone comes to you saying they can do it in O(logn) then you know it's not true. coz that means their algorithm will find the biggest by not looking at every number which is not possible. So now you conclude that O(n) is the Essential complexity of the problem. Sounds good?

Where does this idea come from? In his famous paper Fred.Brooks brings up this notion of software systems having their essential and accidental complexities in the search of a silver bullet for software engineering problems. In summary, Accidental complexity is something that we bring on ourselves into the problem and Essential complexity is something inherent to the problem itself.

refs..

"No Silver Bullet"- Essence and Accidents of Software Engineering
by Frederick P. Brooks, Jr.,
University of North Carolina at Chapel Hill

[1] F.P. Brooks, The Mythical Man-Month, 1985, Addison-Wesley, Reading, Mass., New York, Chapter 16