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 $n<em>0$ such that $f(n) ≤ c \cdot g(n)$ for $n ≥ n</em>0$.
• 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