1. Performance Analysis

Performance Analysis of Algorithms

Introduction to Programming

  • Programming: The process of representing data and solving problems using that data.

  • Components: Data Structures and Algorithms are fundamental to programming.

Performance of Algorithms

  • Performance can be computed through:

    • Empirical Approach: Based on actual execution (A Posteriori Testing).

    • Theoretical Approach: Assumes factors like processor speed are constant (A Priori Analysis).

A Priori Analysis

  • Definition: Theoretical analysis of an algorithm's efficiency.

  • Assumptions: All external factors are negligible.

A Posteriori Testing

  • Definition: Empirical analysis of the chosen algorithm.

  • Process:

    1. Implement the algorithm in a programming language.

    2. Execute on a specific machine.

    3. Collect real statistics (running time and memory usage).

Comparison of Approaches

  • Priori Analysis:

    • Done on algorithms.

    • Independent of programming languages and underlying hardware.

  • Posterior Testing:

    • Done on implemented programs.

    • Dependent on the chosen language and the hardware specifics (OS, processor).

Definition of Algorithm

  • Definition: A finite set of well-defined instructions to solve a problem.

    • Characteristics:

      • Input: Zero or more inputs.

      • Output: At least one result.

      • Definiteness: Clear and unambiguous.

      • Finiteness: Must terminate after a finite number of steps.

      • Effectiveness: Instructions must be executable by a machine.

    • Algorithms differ from programs, as programs may not always terminate.

Algorithm Specification

  • How to express algorithms:

    • High-level description.

    • Natural language.

    • Graphic representation (e.g., flowcharts).

    • Pseudocode: Language-independent informal description.

    • Formal implementation descriptions (C, C++, Java, etc.).

Algorithm Analysis

  • Criteria for evaluation:

    • Efficiency in storage use.

    • Acceptable running time for the task.

  • Performance Analysis: Estimating time and space complexity.

Time Complexity Example

  • Function: void search(int arr[], int len, int target)

    • Time Complexity: O(n)

    • Space Complexity: Constant space usage (O(1)).

Space Complexity

  • Definition: Total memory needed to complete an algorithm.

  • Formula:

    • S(P) = Fixed Part + Variable Part

    • Fixed Part: Independent of input (code space, constants).

    • Variable Part: Dependent on problem instance (variable space, recursion).

Examples of Space Complexity

  • Algorithm abc(a, b, c): Constant space usage (O(1)).

  • Algorithm Sum(a, n): Linear space complexity (O(n)).

  • Algorithm RSum(a, n): Higher space complexity due to recursion (O(n)).

Time Complexity of Common Algorithms

  1. Swapping Algorithm:

    • Time Complexity: O(1) (constant time).

  2. Addition of Two Numbers:

    • Algorithm: sum(A, n)

    • Time Complexity: O(n).

  3. Addition of Square Matrices:

    • Algorithm: add(A, B, n)

    • Time Complexity: O(n²).

  4. Multiplication of Square Matrices:

    • Algorithm: Multiply(A, B, n)

    • Time Complexity: O(n³).

  5. For Loops Variations:

    • Complexity varies with conditions (O(1), O(log n)).

Asymptotic Notations

  • Used to describe running time complexity:

    • O-notation (Big O): Upper bound (worst case).

    • Ω-notation (Big Omega): Lower bound (best case).

    • Θ-notation (Theta): Average bound (best and worst case are equal).

  • Comparative Classes: Ordering of complexity from constant (O(1)) to factorial (O(n!)).

Analyzing Time Efficiency

  • Steps include determining input size, identifying basic operations, and formulating execution counts.

  • Basic Operations: Key operations that predominantly consume time:

    • e.g., Key comparisons in searches and arithmetic operations in calculations.

Example Problem: Element Uniqueness

  • Check for distinct elements:

    for i from 0 to n-2:
    for j from i+1 to n-1:
        if A[i] == A[j]: return false
return true

  • Complexity: O(n²).

Recursive Algorithm Example: Factorial

  • Algorithm: F(n) computes n! recursively.

  • Running Time Analysis:

    • Recurrence relation reflects additional calls, affecting time complexity.

Towers of Hanoi

  • Recursive method for disk movement:

    TowersOfHanoi(n, source, destination, spare) {
  if (n == 1) print move detail
  else {
    TowersOfHanoi(n-1, source, spare, destination);
    print move detail;
    TowersOfHanoi(n-1, spare, destination, source);
  }
}

  • Time Complexity: Characterized by exponential growth.

Master Theorem for Recurrence Relations

  • Application for analyzing recursive algorithms under divide and conquer strategies, with established cases for bounds on T(n).

  • General Form: T(n) = aT(n/b) + O(n^k).

    • Different cases assess growth rates depending on constants a, b, and k.