Algorithm Analysis

Problem Solving Steps

  • Problem definition.
  • Algorithm design/specification.
  • Algorithm analysis.
  • Implementation.
  • Testing.
  • Maintenance.

Algorithm Design/Specifications

  • Algorithm: A finite set of instructions to accomplish a task.
  • Description: Use natural language, pseudo-code, diagrams, etc.
  • Criteria:
    • Input: Zero or more quantities.
    • Output: One or more quantities.
    • Definiteness: Clarity and precision.
    • Finiteness: Must stop after a finite number of steps.
    • Effectiveness: Each instruction must be basic and feasible.

Algorithm Analysis

  • Space complexity: How much space is required.
  • Time complexity: How much time to run the algorithm.

Space Complexity

  • Definition: The amount of memory required for an algorithm to run to completion.
  • Components:
    • Fixed part: Independent of the problem size (e.g., name of data collection).
    • Variable part: Dependent on the problem size (e.g., actual text).
  • Formula: S(P) = c + S(instance characteristics), where c is a constant.

Time Complexity

  • Often more important than space complexity.
  • Measured by worst case.

Running Time

  • Varies with inputs and typically grows with the size of the inputs.
  • Focus on relative rates of growth with respect to the input size.
  • Worst case running time is easier to analyze and crucial for certain applications.
  • Experimental Approach Limitations:
    • Requires implementation, which can be time-consuming.
    • Results may not generalize to other inputs.
    • Requires same hardware and software for comparison.
  • Theoretical Approach:
    • Uses high-level descriptions instead of language-dependent implementations.
    • Enables hardware and software-independent evaluation.

Pseudocode

  • High-level description of an algorithm.
  • More structured than English, less detailed than a program.
  • Control flow:
    • if … then … [else …]
    • while … do …
    • repeat … until …
    • for … do …
  • Indentation replaces braces.

Primitive Operations

  • Basic computations performed by an algorithm.
  • Independent of the programming language.
  • Examples: Evaluating an expression, assigning a value, calling/returning from a method.

Low Level Algorithm Analysis

  • Based on primitive operations.

Estimating Running Time

  • Running time T(n) is bounded by linear functions.

Growth Rate of Running Time

  • Unaffected by constant factors.
  • Examples: Linear ≈ n, Quadratic ≈ n^2, Cubic ≈ n^3

Asymptotic Notation

  • Big-Oh Notation: f(n) is O(g(n)) if there exist positive constants c and n0 such that f(n) ≤ c \cdot g(n) for n ≥ n0.
  • Simple Rule: Drop lower order terms and constant factors.

Big-Oh and Growth Rate

  • Gives an upper bound on the growth rate of a function.
  • Ranks functions according to growth rate.

Big-Oh Rules

  • Drop lower-order terms and constant factors.
  • Use the smallest possible functions.
  • Use the simplest expression of the class.

Properties of Big-Oh

  • If f(n) is O(g(n)), then af(n) is O(g(n)) for any a.
  • If f(n) is O(g(n)) and h(n) is O(g'(n)), then f(n) + h(n) is O(g(n) + g'(n)).
  • Other properties include multiplication and transitivity.

Asymptotic Analysis Terminology

  • Logarithmic: O(log n)
  • Linear: O(n)
  • Quadratic: O(n^2)
  • Polynomial: O(n^k), k ≥ 1
  • Exponential: O(a^n), n > 1

Computing Prefix Averages

  • Quadratic Time: O(n^2)
  • Linear Time: O(n)

Running Time Calculations - General Rules

  • FOR loop: Number of iterations times the time of the inside statements.
  • Nested loops: Product of the number of iterations times the time of the inside statements.
  • Consecutive Statements: Sum of running time of each segment.
  • If/Else: Testing time plus the larger running time of the cases.

Logarithms in the Running Time

  • An algorithm is O(log N) if it takes constant time to cut the problem size by a fraction (usually ½).

“Relatives” of Big-Oh

  • Big Omega Ω(f(n)): Asymptotic lower bound.
  • Big Theta Θ(f(n)): Asymptotic tight bound.
  • Little-oh: f(n) is o(g(n)) if f(n) is O(g(n)) and f(n) is not Θ(g(n)).

Important Series

  • Sum of squares: ∑^N_{i=1} i^2 ≈ (N(N+1)(2N+1))/6
  • Sum of exponents: ∑^N_{i=1} i^k ≈ N^{k+1} /(k+1)
  • Geometric series: ∑^N_{i=0} A^i = (A^{N+1} - 1) / (A - 1)
  • Special case when A = 2: ∑^N_{i=0} 2^i = 2^{N+1} - 1

ADT (Abstract Data Types)

  • A logical view of the data objects together with specifications of the operations required to create and manipulate them.

What is a data type?

  • A set of objects, each called an instance of the data type.
  • A set of operations.
  • Each object must have some representation.
  • Each operation must have some implementation.

Two varieties of data types

  • Opaque data types in which the representation is not known to the user.
  • Transparent data types in which the representation is profitably known to the user

Why are opaque data types better?

  • Representation can be changed without affecting user.
  • Forces the program designer to consider the operations more carefully