LS03_Complexity

CSE 373 Algorithm Analysis and Runtime Complexity

Overview

  • Created by Marty Stepp

  • University of Washington, all rights reserved.

Evaluating an Algorithm

Key Considerations

  • Purpose: To determine the performance of a given algorithm.

  • Method:

    • Implement the algorithm.

    • Run and time it across multiple trials to average the results.

Pros

  • Real-world performance measurement.

  • Identifies system effects on algorithm performance.

  • Stress testing can provide insights into dynamic environments.

  • No mathematical analysis required.

Cons

  • Requires time-consuming code implementation.

  • Performance estimation can be challenging.

  • When comparing algorithms, all conditions (e.g., same hardware) must be controlled.

Range Algorithm

Initial Implementation

  • Purpose: Returns the range (difference between max and min) of values in an array.

public static int range(int[] numbers) {
    int maxDiff = 0;
    for (int i = 0; i < numbers.length; i++) {
        for (int j = 0; j < numbers.length; j++) {
            int diff = Math.abs(numbers[j] - numbers[i]);
            if (diff > maxDiff) {
                maxDiff = diff;
            }
        }
    }
    return maxDiff;
}

Improved Version

  • Efficiency: A slight enhancement by narrowing inner loop.

public static int range(int[] numbers) {
    int maxDiff = 0;
    for (int i = 0; i < numbers.length; i++) {
        for (int j = i + 1; j < numbers.length; j++) {
            int diff = Math.abs(numbers[j] - numbers[i]);
            if (diff > maxDiff) {
                maxDiff = diff;
            }
        }
    }
    return maxDiff;
}

Much Faster Version

  • Efficiency: A significantly optimized approach to compute range.

public static int range(int[] numbers) {
    int max = numbers[0];
    int min = max;
    for (int i = 1; i < numbers.length; i++) {
        if (numbers[i] < min) {
            min = numbers[i];
        }
        if (numbers[i] > max) {
            max = numbers[i];
        }
    }
    return max - min;
}

Runtime Comparisons

Performance Measurement: Different Versions

  • Version 1: Time consumption peaks at 60000ms for larger N.

  • Version 2: More efficient with better runtime as size increases.

  • Version 3: Drastically reduced runtime down to 1800ms.

Analyzing Efficiency

Definition of Efficiency

  • Efficiency: Resource utilization of code with a focus on runtime but can include memory usage.

Analysis Approach

  • Assume that single statements in Java take a constant time.

  • Total runtime equals the sum of individual statement runtimes.

  • Conditional runtimes reflect the chosen path (if/else structure).

  • Runtime of loops is dependent on the number of iterations multiplied by the body execution time.

Runtime Example

  • Code Structure:

    • Statements executed in sequence.

    • Nested loops where inner loop runs for half the outer loop.

  • Analysis Cases:

    • Calculate execution for N = 10 and N = 1000.

Algorithm Growth Rates

Concept of Growth Rates

  • Runtime is represented in relation to input size N.

  • Focusing on the highest-order term when N is large.

  • Notation - Big-Oh notation helps categorize growth.

    • For example, 0.4N³ + 25N² + 8N becomes O(N³).

Growth Rate Examples

Visual Observations

  • Different functions exhibit varied growth behaviors.

    • Comparison of algorithms based on their runtime as data size increases.

Large N Behavior

  • Analyzing differences and overlaps in behavior at high values of N.

Complexity Classes

Categories of Efficiency

  • Big-Oh Classifications:

    • Constant: O(1) - Runtime unchanged.

    • Logarithmic: O(log2 N) - Slow increase.

    • Linear: O(N) - Doubles as input doubles.

    • Log-linear: O(N log2 N) - Slightly more than doubling.

    • Quadratic: O(N²) - Quadruples.

    • Cubic: O(N³) - Multiplies by 8.

    • Exponential: O(2ⁿ) - Drastic increases.

Big-Oh Defined

Formal Definition

  • Asymptotic Upper Bound: f(N) = O(g(N)) if there exist positive constants where f(N) is less than c.g(N) for sufficiently large N.

Focus Areas

  • Growth patterns of functions as N approaches infinity.

  • Ignore small N and constant factors for analysis.

Common Big-Oh Questions

Evaluating Statements

  • Examples of statements evaluated for big-oh classification (e.g., N + 2? O(N) yes).

Preferred Big-Oh Usage

Best Practices

  • Choose the tightest bounds for efficiency classification.

  • Ignore constant factors and lower order terms.

Incorrect Practices

  • Avoid expressions suggesting improper relationships (e.g., f(N) < O(g(N)) is wrong).

Basic Big-Oh Proof Example

  • Claim: 2N + 6 = O(N)

  • Proof Overview:

    • Find values of C and No such that condition holds for all N > No.

Math Background: Exponents

Key Concepts

  • Exponent Definition: X^Y means X multiplied by itself Y times.

  • Useful identities illustrated with examples.

Math Background: Logarithms

Logarithm Definition

  • Definition: X^A = B means logx B = A.

  • Includes examples demonstrating application and base conversions.

More Runtime Examples

Runtime Calculations

  • Simple Examples of increasing complexity classes (e.g., int sum = 0; for loop example).