Basics+of+Algorithm+Analysis

Module Overview

Definition: An algorithm is a sequence of unambiguous instructions that solve a problem, producing a required output for all legitimate inputs within a finite time.
Correctness: An algorithm is correct if it consistently produces the right answer for valid inputs within a finite time.
Characteristics:
- Unambiguity must remain uncompromised.
- Input range for the algorithm must be clearly defined.
- Multiple representations or algorithms may exist for a single problem.

Etymology: The term "algorithm" originates from the mathematician Abu Abdullah Muhammad ibn Musa al-Khwarizmi (circa 780–850 AD), a key figure in the development of algebra.
Contribution: Notable works include "On calculating with Hindu numerals" and "Algoritmi de numero Indorum."

Data Structures: Methods to store information that allow for particular operations, e.g., linked lists, hash tables, heaps, red-black trees.

Euclid’s Algorithm: Repetitively applies the formula gcd(m, n) = gcd(n, m mod n).
- Example: gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12.
- Algorithm Steps
  1. If n = 0, return m.
  2. Set r as remainder of m divided by n.
  3. Set m = n and n = r. Repeat until n = 0.

Consecutive Integer Checking Algorithm
- Step-by-step checks from the minimum of m and n down to find GCD lengthens the process and is thus less efficient than Euclid’s Algorithm.
Middle-School Procedure: Involves prime factorization but lacks clarity in definition for unambiguous execution.

Theoretical Importance: Central to computer science; optimization of solving computational problems.
Practical Importance: Provides a toolbox of known algorithms useful for designing and analyzing solutions to new problems.

Purpose:
- To assess characteristics and suitability for applications.
- To uncover potential improvements.
- To provide insight into algorithm efficiency—both time and space.

Chart performance metrics through the number of primitive operations executed.
Assume random-access machines for algorithm performance analysis to maintain consistency and comparability.

Best Case: Minimum execution time.
Average Case: Average execution time across various inputs.
Worst Case: Maximum execution time for the most complex input, useful for performance guarantees.

Definition: A simple sorting algorithm that builds a sorted array one element at a time.
Best-Case Complexity: Occurs when elements are already sorted; complexity θ(n).
Worst-Case Complexity: Happens when elements are in reverse order; complexity θ(n²).
Average-Case Complexity: Generally considered to also be θ(n²).

Defines the running time of algorithms through relative growth in mathematical terms.
Asymptotic notation clarifies behavior as input size approaches infinity.

Focus on dominant terms in complexity, ignoring lower-order terms as inputs grow larger.

Comparison of logarithmic, linear, polynomial, and exponential functions shows various growth rates and their implications, particularly with large inputs.

Big-Oh (O): Denotes an upper bound of running time.
Little-Oh (o): Indicates a non-tight asymptotic upper bound.
Big-Omega (Ω): Indicates a lower bound of running time for best-case scenarios.
Little-Omega (ω): Denotes a non-tight asymptotic lower bound.
Theta (Θ): Represents both lower and upper bounds, indicating tight bounds on growth.

Rules for applying asymptotic notations focus on polynomial terms and simplifications relevant in evaluating growth relative to real-world performance.