Summation notation, recurrence relations, exponentiation, oh my! Analyzing algorithms is hard… but it doesn’t have to be.
Today I see more and more people break into the field of software development without having a formal computer science background. With all of the self-help books, courses, code camps, and online resources out there, I’m sure this trend will only grow. I think that lowering the barrier to enter into software development is a great thing and some of the best developers I have worked with do not have any formal computer science education. However, in a rush to learn the latest framework and programming language, it’s easy to skip over some of the fundamentals of computer science.
The skill of analyzing algorithms is one such fundamental skill that is easy to overlook. It is a skill that, in some types of software development is only rarely needed and often you can go pretty far without ever developing this skill. However, it will inevitably come up if you are a software developer for long enough. Not knowing how to analyze an algorithm could mean that a particular feature consumes 1000 times more resources, or worse yet, the feature is deemed impossible or severely compromised as a result.
I pulled out one of my old college books, Introduction to Algorithms by Cormen et al., and flipped through the first few chapters. I’ve often heard this book described as the authoritative text on analysis of algorithms, but after reviewing it now, it’s not hard to see why learning even the basics could seem like a daunting task to any developer without a solid math background. Concepts like summation notation, matrix multiplication, exponentiation, recurrence relations, the master theorem, and probabilistic analysis fill the first few chapters. Now, I do realize that the book is designed to be a college textbook (and, don’t get me wrong, it really is an excellent textbook), but I think many developers get lost in the details and discouraged when 80% of the topic is actually relatively accessible and easy to understand and remember if approached in the right way. The following will be my attempt to distill the fundamentals of algorithm analysis in a practical way that you can use at your job today.