1. Intro to Algorithm Complexity Analysis

Introduction to Algorithm Complexity Analysis

  • V = S^3, V = 13B, V = Bh, V = 18/Bh

Analysis of Algorithms

  • Measure how fast a program/algorithm runs.

  • Efficiency can be measured by:

    • Execution Time (Time Complexity)

      • Total running time estimated by counting functions in the algorithm.

    • Memory Required (Space Complexity)

Time Complexity

  • T(n): Measure of time required to execute an algorithm.

  • Factors that do not affect time complexity analysis:

    • Programming language used

    • Quality of compiler

    • Speed of computer

Time Complexity Analysis (TCA)

  • Objectives of TCA:

    • Determine feasibility of an algorithm.

    • Compare different algorithms.

  • Tool to explain behavior as input size increases.

    • E.g., if it takes 1 second for input size 1000, how will it behave for size 2000?

Motivation for TCA

  • Understand potential performance of algorithms as user input scales (e.g., 1000 vs. 2000 users).

  • Measure small inputs to predict behavior for larger inputs.

States of Time Complexity Analysis

  • Worst-case: Upper bound on running time for any input size.

  • Average-case: Assumes all inputs are equally likely.

  • Best-case: Lower bound on running time.

Time Complexity Examples

  • Sequential Search in List of Size n:

    • Worst-case: n comparisons.

    • Best-case: 1 comparison.

    • Average-case: n/2 comparisons.

Big-O Notation

  • Represents time complexity as O(f(n)).

  • f(n): Algorithm's growth-rate/instruction-count function.

Analyzing f(n)

  • Focus on worst-case instruction count; e.g. f(n) = 6n + 4.

    • Drop constant terms for large n: f(n) = 6n then to f(n) = n.

    • Describes linear-time algorithm: O(n).

Big-O Analysis with Nested Loops

  • Independent Nested Loops:

    • Running time: O(n^3).

  • Dependent Nested Loops:

    • Running time: O(n^2).

Example Algorithms for Computing Sums**

  • Algorithm A: O(n)

  • Algorithm B: O(n^2)

  • Algorithm C: O(1) - using formula.

Growth Rates

  • Constant time: fixed number of steps.

Big-O Analysis Summary

  • Complexity determined by most frequently executed statements.

  • Constant time complexity: O(1).

Array Based Implementation

  • Adding Entry: O(1) method.

  • Searching Entry: O(1) best case, O(n) worst/average case.

Linked Implementation

  • Adding Entry: O(1) method.

  • Searching for Entry: O(1) best case, O(n) worst case.

Conclusion

  • Algorithm performance analysis helps understand behavior under various input sizes.