Did you apply computational complexity theory in real life?

Question

I'm taking a course in computational complexity and have so far had an impression that it won't be of much help to a developer. I might be wrong but if you have gone down this path before, could you please provide an example of how the complexity theory helped you in your work?

Answer 1

Hi,

Good question, the short answer is it is absolutely essential, and in fact, you wont get past most job interviews as a software engineer if you do not know the basics of computational complexity and its notation system (Big O, theta, omega). As a "developer" it will be of little use because developers are usually not considered engineers. It's not a hard and fast rule but usually a web/ios/ backend developer can get a job at a company (albeit not a really good one) without having gone through essential computer science corse classes, or having an understanding thereof. But do yourself a favor and really learn this stuff, it will earn you a lot of respect even if you just want to be a developer.

Now for your example, it happens a lot when you are parsing through data. You might have hundreds of millions of rows of data, pertaining to unique users and their individual actions on the site, you would like to understand what are the most common 3 page sequences that all users visit. So in order to that, you can write a very inefficient algorithm that goes through each line of input and collect all the actions of a single user, then sort all of those actions. Lets stop here before applying the rest of the algorithm to solve the problem, already you are going through N items in a very large data set (in the hundreds of millions), for each data point in that set you are going through every other data point N -1 (-1 because you are already at 1 before you consider the rest)...you would be doing this just to collect the rest of the client actions, identified in the row that you were looking at. This piece of the algorithm it self is what we call "quadratic time" because it is N* (N -1) = O(N^2)

Not very efficient and will take a long time in real life, not considering the rest of the processing you have to do to find the most common 3 page visits for ALL users. Amazon usually gives interview questions for software engineers which I feel are directly related to the real world work they are doing, I'm not allowed to talk directly about my work other than we use it for processing large data sets as one example. Check out amazon related problems here:

https://leetcode.com/discuss/interview-question/460127/