Complexity analysis and master theorem
The time and space complexity analysis is an integral part of any interview round. Understanding of time complexity allows us to do trade-offs and optimize solutions. If you cannot correctly compute the time or space complexity of the solution, your chances of clearing the interview round decrease dramatically.
In this lesson, we focus on time and space complexity computations, the common types of complexities, and understand Master Theorem to find the complexity of recursive functions.
- Complexity: Amortized complexity, asymptotic equivalent, worst case, and Big O.
- Different types of complexities and their functions
- Master Theorem and examples.
- Problems to identify time and space complexity.