3 Complexity Analysis
This chapter covers
- Understanding why complexity analysis is important.
- Analyzing complexity using big O notation.
- Solving using an algorithm with improved time complexity.
- Reducing the space complexity of an algorithm.
- Recognizing the role of complexity analysis in Bronze-level questions.
Writing efficient algorithms is at the very heart of solving computer science problems. Granted, given a problem, the first step is to find a solution. However, in many practical cases, the next step is to verify that this solution is feasible and useful. This is where complexity analysis comes in.
For example, consider the problem of finding the shortest route between two points on a map. You leave your home, get into the car, and want to find the way to a theater downtown. You enter the address in your GPS, and wait for the answer. Behind the scenes, an algorithm searches for a few plausible routes, and finds (say) 10 candidates. Then, the algorithm needs to choose the best one among these and present it to you. The algorithm weighs these routes according to traffic conditions, length of the route, speed limits, and other factors. Eventually, the algorithm presents you with one or two options, and you can start driving. The algorithm did a lot of work. But you haven’t even noticed because the whole process took less than a second or two. If it had taken 10 minutes, you would have noticed, and complained.