CSEN102 Introduction to Computer Science: Lecture 8: Attributes of Algorithms and Measuring Efficiency
This lecture for CSEN102: Introduction to Computer Science, given by Milad Ghantous, PhD, delves into the attributes that define good algorithms and methods for measuring their efficiency.
8.1 Desirable Attributes of Algorithms
Beyond simply providing a correct solution, an effective algorithm should possess several key attributes:
- Correctness: The algorithm must produce the correct output for all valid inputs and meet the problem's specifications. This is the most fundamental attribute.
- Clarity and Readability: The algorithm should be easy to understand and follow, both for the person who wrote it and for others. This is crucial for maintenance and collaboration.
- Efficiency: The algorithm should use computational resources (time and space) as effectively as possible. This is often quantified by its time complexity and space complexity.
- Finiteness: As previously discussed, an algorithm must terminate after a finite number of steps.
- Generality: An algorithm should be designed to solve a class of problems rather than just a single, specific instance.
- Robustness: The algorithm should handle unexpected or invalid inputs gracefully, without crashing or producing nonsensical results.
- Maintainability: It should be easy to modify, update, and fix issues in the algorithm over time.
8.2 Measuring Algorithm Efficiency
Measuring an algorithm's efficiency typically involves assessing how its performance (time taken or space used) scales with the size of the input. This is often done using "Big O" notation.
1. Time Complexity:
Refers to the amount of time an algorithm takes to complete as a function of the length of its input. It's not about actual time (which varies by hardware) but about the number of elementary operations performed.
- Counting Operations: One way to analyze time complexity is to count the number of basic operations (e.g., arithmetic operations, comparisons, assignments) an algorithm performs.
- Worst-Case, Best-Case, Average-Case:
- Worst-Case: The maximum number of operations an algorithm might perform for a given input size. This is usually what we focus on for guarantees.
- Best-Case: The minimum number of operations.
- Average-Case: The expected number of operations for typical inputs.
2. Space Complexity:
Refers to the amount of memory space an algorithm needs to run to completion as a function of the length of its input. This includes both the input data storage and any auxiliary space used by the algorithm.
8.3 Asymptotic Analysis and Big O Notation (O-notation)
Asymptotic analysis describes the limiting behavior of an algorithm as the input size grows very large. Big O notation is a mathematical notation that describes the upper bound of an algorithm's running time or space requirements.
Common Time Complexities (from fastest to slowest):
- O(1) - Constant Time: The time taken is independent of the input size. (e.g., accessing an array element by index).
- O(log n) - Logarithmic Time: The time increases very slowly with the input size. Often seen in algorithms that divide the problem into smaller halves (e.g., binary search).
- O(n) - Linear Time: The time taken grows proportionally to the input size. (e.g., traversing a list once).
- O(n log n) - Linearithmic Time: Common in efficient sorting algorithms (e.g., Merge Sort, Quick Sort).
- O(n^2) - Quadratic Time: The time grows quadratically with the input size. Often involves nested loops processing all pairs of elements (e.g., simple sorting algorithms like Bubble Sort, selection sort).
- O(2^n) - Exponential Time: The time doubles with each additional input. Very inefficient for even moderately sized inputs (e.g., some brute-force algorithms).
- O(n!) - Factorial Time: The time grows extremely rapidly. Impractical for most real-world problems.
Why Big O Notation?
- It provides a high-level understanding of an algorithm's performance.
- It allows us to compare algorithms independently of hardware or specific programming language.
- It focuses on the dominant term in the growth rate, ignoring constant factors and lower-order terms.
8.4 Practical Considerations for Efficiency
While theoretical efficiency (Big O) is important, practical considerations also play a role:
- Constant Factors: For small input sizes, an algorithm with a higher Big O but a smaller constant factor might perform better.
- Memory Hierarchy: How an algorithm accesses memory (e.g., cache performance) can affect its actual running time.
- Input Distribution: Average-case performance might be more relevant than worst-case for typical inputs.
Thank you