6.1210 Introduction to Algorithms

Definition of an algorithm

An algorithm is a procedure for solving a computational problem.

• In this class, we want algorithms that are correct and efficient.

An algorithm is correct when it gives a correct answer for every possible input. An algorithm is efficient if it uses few resources (number of operations, memory, etc.).

Efficiency

• 🔑 We measure resource usage asymptotically as a function of the input size.
• 📍 We start with worst-case analysis: for all input of the same size $n$, we measure the resources used on the worst possible input.
  • Later in the course, we discuss average-case analysis.
• For an algorithm $A$, we denote the runtime of $A$ on the worst input of size $n$ as $T(n)$

Asymptotic notation

1. Upper bounds: $A$ has worst-case runtime $O(f(n))$ iff there exists a constant $c>0$ and $n_0 \geq 1$ such that, for all $n > n_0$, and for every input $x$ of length $n$, algorithm $A$ uses no more than $c \cdot f(n)$ operations on input $x$. [similar structure to the definition of convergence in real analysis?]
2. Lower bounds: $A$ has worst-case runtime $\Omega(f(n))$ iff there exists a constant $c>0$ and $n _0 \geq 1$ such that, for all $n > n_0$, there exists an input $x$ of length $n$, such that algorithm $A$ uses at least $c \cdot f(n)$ operations on input $x$.