Intro to General Algorithms

Foundations

This note introduces fundamental concepts related to algorithms. We will define what an algorithm is, discuss its essential properties, and explore different ways to analyze their efficiency.

What is an Algorithm?

An algorithm is a well-defined, finite sequence of unambiguous instructions designed to solve a specific problem or perform a particular task. Think of it as a recipe that precisely outlines the steps needed to achieve a desired outcome. Let’s break down this definition:

Well-defined: Each step must be clear and leave no room for interpretation.
Finite: The algorithm must terminate after a finite number of steps. It cannot run forever.
Sequence: The steps must be executed in a specific order.
Unambiguous: Each step must have only one possible interpretation. There should be no ambiguity about what action to take.
Solves a specific problem: The algorithm must be designed to address a particular problem or accomplish a defined task.

Example: A simple algorithm to find the largest number in a list:

Set largest to the first element of the list.
For each remaining element in the list:
- If the element is greater than largest, update largest to the value of the element.
Return largest.

Properties of Algorithms

A good algorithm typically exhibits the following key properties:

Correctness: The algorithm must produce the correct output for all valid inputs. This is the most crucial property.
Finiteness: As stated earlier, the algorithm must terminate after a finite number of steps.
Definiteness: Each step must be precisely defined and unambiguous.
Input: An algorithm must accept zero or more inputs.
Output: An algorithm must produce at least one output.
Effectiveness: Each step should be sufficiently basic that it can, in principle, be carried out by a person using only pencil and paper. This ensures that the steps are feasible and not overly abstract.
Generality: The algorithm should be applicable to a wide range of inputs, not just a specific instance of the problem.

Algorithm Design Techniques

There are several common strategies used to design algorithms:

Brute Force: Systematically trying all possible solutions. This approach is often inefficient but guarantees a solution if one exists. Example: Checking every possible key to open a lock.
Divide and Conquer: Breaking down a problem into smaller subproblems, solving them recursively, and combining the solutions. Example: Merge Sort, Quick Sort.
Greedy Algorithms: Making locally optimal choices at each step with the hope of finding a global optimum. Example: Dijkstra’s algorithm for shortest paths.
Dynamic Programming: Breaking down a problem into overlapping subproblems, solving each subproblem only once, and storing the solutions to avoid redundant computations. Example: Finding the Fibonacci sequence.
Backtracking: Incrementally building a solution, and abandoning a partial solution (“backtrack”) as soon as it determines that the partial solution cannot possibly be completed to a valid solution. Example: Solving Sudoku puzzles.

Algorithm Analysis

In this part, we will explore how to analyze algorithms and compare their efficiency. This involves quantifying the resources an algorithm consumes, primarily time (how long it takes to run) and space (how much memory it uses).

Analyzing Algorithm Efficiency

We analyze algorithms to understand their performance characteristics and choose the most efficient solution for a given problem. Instead of measuring the actual running time, which can vary depending on hardware and implementation, we focus on the growth rate of an algorithm’s resource consumption as the input size ( $n$ ) increases. This is known as asymptotic analysis.

Big O Notation

Big O notation ( $O$ ) provides an upper bound on the growth rate of a function. It describes the worst-case scenario for an algorithm’s performance. Formally, we say that a function $f (n)$ is $O (g (n))$ if there exist positive constants $c$ and $n_{0}$ such that:

$0 \leq f (n) \leq c \cdot g (n) for all n \geq n_{0}$

This means that for sufficiently large inputs ( $n \geq n_{0}$ ), $f (n)$ is bounded above by a constant multiple of $g (n)$ .

Common Big O Notations:

$O (1)$ - Constant Time: The algorithm’s runtime is independent of the input size. Example: Accessing an element in an array.
$O (lo g n)$ - Logarithmic Time: The runtime increases logarithmically with the input size. Example: Binary search.
$O (n)$ - Linear Time: The runtime increases linearly with the input size. Example: Searching for an element in an unsorted list.
$O (n lo g n)$ - Linearithmic Time: The runtime is a product of the input size and its logarithm. Example: Merge Sort, Quick Sort (average case).
$O (n^{2})$ - Quadratic Time: The runtime increases quadratically with the input size. Example: Nested loops iterating over the input. Bubble Sort, Selection Sort, Insertion Sort.
$O (2^{n})$ - Exponential Time: The runtime doubles with each increase in the input size. Example: Finding all subsets of a set.
$O (n!)$ - Factorial Time: The runtime grows factorially with the input size. Example: Traveling Salesperson Problem (brute-force).

Example: Analyzing a Loop

Consider the following code snippet:

for i in range(n):
  for j in range(n):
    print(i, j)

The outer loop runs $n$ times, and for each iteration, the inner loop also runs $n$ times. Therefore, the print statement is executed $n * n = n^{2}$ times. The time complexity of this code is $O (n^{2})$ .

Other Asymptotic Notations

Besides Big O notation, other notations are used to describe algorithm performance:

Big Omega ( $Ω$ ): Provides a lower bound on the growth rate - best-case scenario. $f (n)$ is $Ω (g (n))$ if there exist positive constants $c$ and $n_{0}$ such that $0 \leq c \cdot g (n) \leq f (n)$ for all $n \geq n_{0}$ .
Big Theta ( $Θ$ ): Provides a tight bound (both upper and lower) on the growth rate - average-case scenario. $f (n)$ is $Θ (g (n))$ if there exist positive constants $c_{1}$ , $c_{2}$ , and $n_{0}$ such that $0 \leq c_{1} \cdot g (n) \leq f (n) \leq c_{2} \cdot g (n)$ for all $n \geq n_{0}$ .

Understanding these notations is crucial for comparing algorithms and choosing the most efficient solution for a given problem.

CS Notes

Explorer