Chapter 3: Algorithm Efficiency Analysis
Introduction to Algorithm Efficiency
Definition
- The process of measuring how well an algorithm performs in terms of time and space requirements
- A way to evaluate and compare different algorithms that solve the same problem
Causes
- Even simple programs can be noticeably inefficient (e.g., multiplication algorithms with different operand sizes)
- Different algorithms solving the same problem can have dramatically different performance characteristics
- A program’s efficiency affects its overall performance and user satisfaction
Goals / Objectives
- To measure efficiency in a way that allows comparison of algorithms independent of hardware and software environments
- To evaluate algorithms without requiring full implementation
- To take into account all possible inputs when assessing performance
Importance
- Program efficiency directly impacts response time and user satisfaction
- Small changes in problem size can cause significant differences in execution time with inefficient algorithms
- Understanding efficiency helps developers choose appropriate algorithms for specific problem sizes and constraints
Procedures
- Not specified in notes
Advantages & Disadvantages
- Not specified in notes
Impact / Effect
- When multiplying 7562 by 423 versus 7562 by 100,000,000, there can be significant delays with certain algorithms
- Efficiency analysis helps predict how algorithms will perform as input sizes grow
Examples
- Multiplication Algorithm 1: Uses repeated addition (product = product + firstOperand in a loop), performs 2n + 1 operations
- Multiplication Algorithm 2: Decomposes the second operand and uses digit-wise multiplication, performs n² + n + 1 operations
- Multiplication Algorithm 3: Uses the formula n × (n + 1) / 2, performs only 4 operations
Experimental Studies
Definition
- A method of measuring algorithm efficiency by implementing the algorithm and running it on various test inputs while recording execution times
Causes
- Need to understand real-world performance of algorithms
- Desire to measure actual running time rather than theoretical estimates
Goals / Objectives
- To collect running times by experimenting with different test inputs of various sizes
- To visualize the relationship between problem size and execution time
- To perform statistical analysis fitting functions to experimental data
Importance
- Provides concrete, measurable data about algorithm performance
- Can reveal actual performance characteristics on specific hardware/software combinations
Procedures
- Implement the algorithm(s)
- Run the program on various test inputs while recording time spent during each execution
- In Java, use
System.currentTimeMillis()method (orSystem.nanoTime()for very quick operations):- Record time immediately before executing the algorithm
- Record time immediately after execution
- Compute the difference to obtain elapsed time
- Plot performance with x-coordinate as input size n and y-coordinate as running time t
- Perform statistical analysis to fit the best function to the experimental data
Advantages & Disadvantages
-
Advantages:
- Provides actual measured performance data
- Shows real-world behavior on specific systems
-
Disadvantages:
- Experimental running times are difficult to directly compare unless experiments are performed in the same hardware and software environments
- Experiments can only be done on a limited set of test inputs, leaving out running times of inputs not included (which may be important)
- An algorithm must be fully implemented before it can be studied experimentally
Impact / Effect
- The visualization provides intuition about the relationship between problem size and execution time
- Meaningful analysis requires choosing good sample inputs and testing enough of them to make sound statistical claims
Examples
- Recording execution time for algorithm runs and plotting them to observe growth patterns
Analysis of Algorithms
Definition
- The process of measuring the complexity of an algorithm without running experiments
- A theoretical approach to evaluating algorithm performance based on counting operations
Causes
- The shortcomings of experimental analysis (hardware dependency, limited inputs, need for implementation)
- Need for a hardware-independent, comprehensive evaluation method
Goals / Objectives
- To evaluate relative efficiency of algorithms independent of hardware and software environment
- To analyze algorithms by studying high-level descriptions without implementation
- To take into account all possible inputs
Importance
- Allows comparison of algorithms before implementation
- Provides hardware-independent measurements
- More comprehensive than experimental analysis as it considers all possible inputs
Procedures
- Count primitive operations performed by the algorithm
- Express the count as a function of input size n
- Focus on worst-case analysis (easier than average-case and leads to better algorithm design)
Advantages & Disadvantages
-
Advantages:
- Hardware and software independent
- No implementation required
- Comprehensive (considers all inputs)
- Easier to perform than experimental studies
-
Disadvantages:
- Does not provide exact execution times
- Requires understanding of algorithm structure and operation counting
Impact / Effect
- Enables algorithm comparison based on growth rates rather than specific execution times
- Helps identify which algorithms scale better as problem size increases
Examples
- Not specified in notes
Types of Complexity
Definition
- Space complexity: The memory required to execute the code
- Time complexity: The time the code takes to execute
Causes
- Different algorithms have different resource requirements
- Both memory and processing time are limited resources
Goals / Objectives
- To measure and understand both memory and time requirements of algorithms
- To make informed trade-offs between space and time when designing algorithms
Importance
- Time complexity is usually more important than space complexity in modern systems
- Understanding both helps in choosing appropriate algorithms for specific constraints
Procedures
- Not specified in notes
Advantages & Disadvantages
- Not specified in notes
Impact / Effect
- There is usually a trade-off between time and space requirements of a program
- Focusing on time complexity is the primary concern in most algorithm analysis
Examples
- Not specified in notes
Counting Primitive Operations
Definition
- Primitive operations are basic computational steps that take constant time
- Examples include: assigning a value to a variable, following an object reference, performing an arithmetic operation, comparing two numbers, accessing a single element of an array by index, calling a method, returning from a method
Causes
- Need for a consistent unit of measurement across different operations
- Difficulty in determining exact execution time for each operation
Goals / Objectives
- To count how many primitive operations an algorithm executes as a measure of running time
- To use operation count as a proxy for actual running time
Importance
- The number of primitive operations correlates to actual running time on specific computers
- Provides a platform-independent way to measure algorithm efficiency
- Operation count is proportional to the actual running time of the algorithm
Procedures
- Identify all primitive operations in the algorithm
- Count how many times each operation is performed
- Sum the total number of operations
- Express this total as a function of input size n
Advantages & Disadvantages
-
Advantages:
- Simpler than measuring exact execution time
- Platform-independent measurement
- Correlates well with actual performance
-
Disadvantages:
- Does not give precise execution time
- Different primitive operations may have slightly different actual costs
Impact / Effect
- Instead of trying to determine specific execution time of each operation, simply counting operations provides sufficient information for efficiency analysis
- The count t of primitive operations is proportional to actual running time
Examples
- For Algorithm A (sum = 0; for i = 1 to n; sum = sum + i):
- Assignments: n + 1
- Additions: n
- Total operations: 2n + 1
Measuring Operations as a Function of Input Size
Definition
- Associating a function f(n) with an algorithm that characterizes the number of primitive operations performed as a function of input size n
Causes
- Need to capture the order of growth of an algorithm’s running time
- Different input sizes lead to different execution times
Goals / Objectives
- To express algorithm efficiency as a mathematical function
- To understand how running time scales with input size
Importance
- Allows prediction of how algorithm performance changes as problem size grows
- Enables comparison of algorithms based on their growth rates
- Provides insight into scalability
Procedures
- Count primitive operations
- Express the count as a function f(n) where n is the input size
- Focus on how the function grows as n increases
Advantages & Disadvantages
- Not specified in notes
Impact / Effect
- The function f(n) characterizes the algorithm’s time requirement
- As problem size increases by some factor, the function value increases proportionally, indicating the increase in time requirement
Examples
- Algorithm A: f(n) = 2n + 1
- Algorithm B: f(n) = n² + n + 1
- Algorithm C: f(n) = 4
Best, Average, and Worst Case Analysis
Definition
- Worst-case analysis: Analyzing algorithm performance for the input that causes maximum operations
- Average-case analysis: Analyzing performance averaged over all possible inputs of the same size
- Best-case analysis: Analyzing performance for the input that causes minimum operations (not emphasized in these notes)
Causes
- Algorithms may run faster on some inputs than others of the same size
- Need to characterize performance across different input scenarios
Goals / Objectives
- To estimate time requirements for different input scenarios
- To provide guarantees about algorithm performance
Importance
- Worst-case analysis is much easier than average-case analysis
- Focusing on worst-case typically leads to better algorithms
- Worst-case provides performance guarantees
Procedures
- For worst-case: Identify the worst-case input and count operations for that input
- For average-case: Define a probability distribution on inputs and compute average operations (much more challenging)
Advantages & Disadvantages
-
Advantages:
- Worst-case analysis only requires ability to identify worst-case input (often simple)
- Leads to better algorithm design by focusing on worst-case performance
- Provides clear performance bounds
-
Disadvantages:
- Average-case analysis is quite challenging as it requires defining probability distributions on inputs
- Worst-case may be overly pessimistic for some algorithms
Impact / Effect
- The actual time needed for an algorithm is difficult to compute accurately, so we estimate times for different cases
- We express time efficiency as a factor of the problem size
Examples
- When searching a collection of data, the problem size is the number of items in the collection
Big O Notation
Definition
- A mathematical notation used to represent an algorithm’s efficiency/complexity
- Expresses the upper bound of growth rate by focusing on the dominant term and ignoring constants
Causes
- Need for a standardized way to express and compare algorithm efficiency
- Actual time requirement cannot be computed precisely
Goals / Objectives
- To provide a simple, standardized notation for algorithm efficiency
- To focus on the most significant factors affecting growth rate
- To enable easy comparison between algorithms
Importance
- Computer scientists use Big O notation as the standard for representing algorithm complexity
- Allows quick comparison of algorithm scalability
- Helps identify which algorithms are suitable for different problem sizes
Procedures
Steps to derive Big O notation:
- Start with the growth-rate function
- Ignore smaller terms in the function
- Ignore constant multipliers/coefficients
- Express result as O(dominant term)
Example derivation:
- If growth-rate function is 4n² + 50n - 10
- Ignore smaller terms: 4n²
- Ignore coefficient: n²
- Result: O(n²)
Advantages & Disadvantages
-
Advantages:
- Simple and standardized notation
- Makes algorithm comparison straightforward
- Focuses on scalability rather than implementation details
-
Disadvantages:
- Does not capture exact performance
- Ignores constant factors that may matter for small inputs
- Different algorithms with same Big O can have different actual performance
Impact / Effect
- As problem size increases, the dominant term in the growth function determines performance
- Constant factors and smaller terms become less significant for large inputs
- Enables predictions about how doubling problem size affects running time
Examples
- Algorithm A: 2n + 1 → O(n) (linear)
- Algorithm B: n² + n + 1 → O(n²) (quadratic)
- Algorithm C: 4 → O(1) (constant)
Verbal expressions:
- “Algorithm A is O(n)” (read as “Big O of n”)
- “Algorithm B is O(n²)”
- “Algorithm C is O(1)“
The Seven Most Common Functions in Algorithm Analysis
Definition
The seven growth-rate functions most frequently encountered when analyzing algorithms: constant, logarithm, linear, n-log-n, quadratic, cubic, and exponential
Causes
- Different algorithmic patterns produce different growth characteristics
- These functions represent common computational patterns
Goals / Objectives
- To understand the typical efficiency classes of algorithms
- To recognize growth patterns when analyzing algorithms
Importance
- These functions span from highly efficient (constant) to impractical for large inputs (exponential)
- Understanding these functions helps predict algorithm behavior
- Enables classification of algorithms into efficiency categories
Procedures
- Not specified in notes
Advantages & Disadvantages
- Not specified in notes
Impact / Effect
- Different functions grow at vastly different rates
- The choice of algorithm (and thus its growth function) dramatically impacts performance for large inputs
Examples
1. Constant Function: f(n) = c
- For any input n, the function assigns the value c
- Characterizes basic operations (adding two numbers, assigning a value, comparing two numbers)
- Example: Algorithm C with 4 operations regardless of n
2. Logarithm Function: f(n) = log_b n
- For some constant b > 1
- Most common base in computer science is 2: log n = log₂ n
- x = log_b n if and only if b^x = n
- For any base b > 0, log_b 1 = 0
- The number of digits in an integer n corresponds to approximately log₁₀ n
3. Linear Function: f(n) = n
- Given input value n, assigns value n itself
- Arises when doing a single basic operation for each of n elements
- Example: Comparing a number x to each element of an array of size n requires n comparisons
4. N-log-n Function: f(n) = n log n
- Grows slightly more rapidly than linear function
- Grows much less rapidly than quadratic function
5. Quadratic Function: f(n) = n²
- Appears in algorithms with nested loops where:
- Inner loop performs linear number of operations
- Outer loop is performed linear number of times
- Results in n × n = n² operations
- Example: Algorithm B with nested loops
6. Cubic Function: f(n) = n³
- Appears less frequently than constant, linear, and quadratic functions
7. Exponential Function: f(n) = b^n
- b is a positive constant (the base)
- n is the exponent
- Most common base in algorithm analysis is b = 2
- Example: Loop that starts with one operation and doubles operations with each iteration performs 2^n operations in nth iteration
Comparing Algorithm Efficiency
Definition
- The process of evaluating relative performance of algorithms based on their growth-rate functions
- Understanding how different algorithms scale as problem size increases
Causes
- Multiple algorithms can solve the same problem with different efficiency
- Need to choose appropriate algorithms for specific problem sizes and requirements
Goals / Objectives
- To understand which algorithms are practical for different problem sizes
- To predict performance differences as input size changes
- To make informed algorithm selection decisions
Importance
- Small differences in efficiency notation (O(n) vs O(n²)) translate to huge performance differences for large inputs
- Understanding growth rates helps avoid choosing algorithms that won’t scale
- Even “inefficient” algorithms may be acceptable for small problem sizes
Procedures
- Compare growth-rate functions
- Consider the effect of doubling problem size:
- O(1): No effect
- O(log n): Negligible increase (adds 1)
- O(n): Doubles
- O(n log n): Doubles and adds 2n
- O(n²): Quadruples
- O(n³): Multiplies by 8
- O(2^n): Squares
Advantages & Disadvantages
- Not specified in notes
Impact / Effect
- For one million items at one million operations per second:
- O(log n): 0.0000199 seconds
- O(n): 1 second
- O(n log n): 19.9 seconds
- O(n²): 11.6 days
- O(n³): 31,709.8 years
- O(2^n): 10^301,016 years
Examples
Growth rate comparison for increasing n:
- When n = 10:
- log n = 3, n = 10, n² = 100, n³ = 1000, 2^n = 1024
- When n = 100:
- log n = 7, n = 100, n² = 10,000, n³ = 1,000,000, 2^n = 10
- When n = 1,000,000:
- log n = 20, n = 1,000,000, n² = 10^12, n³ = 10^18, 2^n = 10^301,030
Practical implications:
- A programmer can use O(n²), O(n³), or O(2^n) as long as problem size is small
- At one million operations per second, it takes 1 second:
- For problem size 1000 with O(n²)
- For problem size 100 with O(n³)
- For problem size 20 with O(2^n)
Visual representations:
- O(n) algorithm: Represented as n sequential operations (like digging n times)
- O(n²) algorithm: Represented as triangular pattern (1 + 2 + 3 + … + n operations)
- Another O(n²) algorithm: Represented as square grid (n × n operations)
Real-World Algorithm Analysis Examples
Definition
- Practical examples demonstrating Big O notation for everyday tasks and code implementations
Causes
- Need to apply theoretical concepts to concrete scenarios
- Understanding complexity through familiar activities helps reinforce concepts
Goals / Objectives
- To practice identifying time complexity in real-world scenarios
- To analyze actual code and determine its Big O notation
Importance
- Bridges theory and practice
- Helps develop intuition for recognizing complexity patterns
Procedures
- Identify the operations being performed
- Count how operations scale with input size
- Express as Big O notation
Advantages & Disadvantages
- Not specified in notes
Impact / Effect
- Reinforces understanding of Big O notation through concrete examples
- Develops skill in analyzing code efficiency
Examples
Everyday activities:
- After arriving at a party, you shake hands with each person: O(n)
- Each person in a room shakes hands with everyone else: O(n²)
- You climb a flight of stairs: O(n)
- You slide down the banister: O(h) where h is height
- After entering an elevator, you press a button: O(1)
- You ride the elevator from ground floor to nth floor: O(n)
- You read a book twice: O(n)
Code example (Exercise 3.2):
public String toString() {
String str = "";
for (int i = 0; i < length; i++)
str += array[i] + "\n";
return str;
}- Analysis: O(n) - The code traverses through each array element to concatenate its value to the string variable str