Unit 2: Introduction to Analysis of Algorithms
In this unit, we explore how we can express an algorithm's efficiency as a function of its input size. The order of growth of running time of an algorithm gives a simple characterization of algorithm's efficiency and allows us to relate performance of alternative algorithms. Asymptotic analysis is based on the idea that as the problem size grows, the complexity will eventually settle down to a simple proportionality to some known function. This idea is incorporated in the "Big Oh", "Big Omega", and "Big Theta" notations for asymptotic performance. These notations are useful for expressing the complexity of an algorithm without getting lost in unnecessary detail.
Completing this unit should take you approximately 9 hours.
2.1: Introduction to Algorithms
Watch this video to learn about the basics of the algorithm.
2.2: Asymptotic Analysis
Watch this video to learn about the ideas behind the use of asymptotic analysis in algorithms.
2.3: Introduction to Analysis of Algorithms
Read the Prologue of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms.
2.4: Master Theorem
Read this article to learn about the use of Master Theorem in analyzing recursive problems.
Complete all questions in this assignment. There are six questions listed in two parts. The first part requires solving the problems using the Master Theorem discussed in the lectures. The second part requires solving for complexity of the algorithms using the first principles. You can check your answers against the Answer Key.