### 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.**

Upon successful completion of this unit, you will be able to:

- Describe asymptotic notations for bounding algorithm running times from above and below.
- Explain methods for solving recurrences useful in describing running times of recursive algorithms.
- Explain the use of Master Theorem in describing running times of recursive algorithms.

### 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.