Algorithm Analysis Comprehensive Notes

Algorithm Analysis by Steve Kreutzer, PhD

Learning Objectives

• Describe empirical and mathematical frameworks for characterizing performance.

• Analyze a code fragment or algorithm to determine its worst-case running time using Big-O notation.

Reasons to Analyze Algorithms

• Predict performance:

  • Estimate how long a program will take to run.

  • Estimate how much extra memory a program will require.

• Compare algorithms:

  • Provide performance guarantees.

Challenge: Measure Algorithm Running Time

• Characterize the running time as a function of the input size, denoted by n.

• n can represent the number of items to be processed or a single value used in computation.

• Running time generally increases with problem size.

• For many algorithms, running time is relatively insensitive to the characteristics of the input data.

Approaches for Evaluating Running Time

• Experimental Studies:

  • Run the program with inputs of varying size.

  • Record the time needed for each input size.

• Theoretical Analysis:

  • Analyze a high-level description of the algorithm.

Experimental Approach: Doubling Test

• Execute the algorithm repeatedly, doubling the input size for each execution.

• Record the time taken for each execution.

• Calculate the doubling ratio (the ratio of running times for consecutive doubling input sizes).

Element Distinctness Problem

• Design an algorithm to determine whether all elements of a list are distinct.

Brute Force Approach

• Check every pair for equality.

• Examine each value in the list and compare it to every value after it.

Leverage Sorting

• Sort the list.

• Compare each value to its neighbor.

• If there are duplicates, they will be adjacent.

• Sorting helps in many problems.

Leverage Hashing

• Use a Set, which relies on hashing (constant time lookup).

  1. Create an empty set.

  2. For each value, determine whether it is already in the set.

     • If it is not in the set, add it to the set.

     • If it is in the set, the list is not distinct; stop.

  3. The elements in the list are distinct if each value has been examined without finding a duplicate in the set.

Doubling Test Results (Worst Case: No Duplicates)

• Algorithm 1 running time quadruples as the input size doubles.

• Algorithm 2 running time doubles as the input size doubles.

Doubling Hypothesis

• A quick way to estimate the exponent b in a power-law relationship.

• Run the program, doubling the size of the input.

• Hypothesis: Running time is approximately a \cdot n^b with b = \log_2 \text{ ratio}.
  *Caveat:. Cannot identify logarithmic factors with doubling hypothesis.

• Caveat: Cannot identify logarithmic factors with doubling hypothesis.

Limitations of Experiments

• Difficult to identify representative data.

• The algorithm must be implemented beforehand.

• Experiments take time and can be done only on a limited number of test inputs.

Theoretical Models for Running Time

• Characterize running time by reviewing a code fragment or pseudo-code.

• Develop a function f(n) to represent the running time, where n is the input size.

  • Examples of n: length of an array, number of records to be processed, or some value n.

Counting Operations and Statements

• If the execution time of an operation or statement takes constant time, count it as 1 unit of time.

• Treat execution times of statements as equivalent.

• This is possible because we care about very large values of n, and as n grows very large, constants become insignificant relative to n (Asymptotic Analysis).

Constant Time vs. Not Constant Time

• Constant Time:

  • Variable declaration

  • Assignment statement

  • Integer compare

  • Array element access

  • Array length

  • Integer addition

• Not Constant Time:

  • Array allocation

  • String concatenation

  • String comparison

  • Loop through an array

  • Array copy

  • Function calls: count the time inside the function

Array Access Example

• The number of array accesses as a function of n in the given code:

int count = 0;
for (int i = 0; i < n; i++)
 for (int j = i+1; j < n; j++)
 if (a[i] + a[j] == 0)
 count++;

• Is \frac{1}{2} n (n - 1)

Asymptotic Analysis

• Characterize the running time and space requirements of an algorithm as the input size (n) becomes very large.

• Let f(n) be the running time (or space) of an algorithm.

Big-O Notation

• Given functions f(n) and g(n), we say that f(n) is O(g(n)) if there are positive constants c and n0 such that f(n) \leq c \cdot g(n) for n \geq n0.

• Objective is to determine g(n).

Common Orders of Growth

Big-O Notation

• Asymptotic: as n becomes very large (approaching \infty).

• Worst-case analysis: Provides a performance guarantee.

• Drop lower order terms and constants.

Rationale

• When n is large, lower-order terms are negligible.

• When n is small, we don’t care.

Tilde Notation

• Drop lower order terms.

Example: 2-SUM

Q. Using \sim notation, how many array accesses as a function of input size n?
A. \sim n^2 array accesses.

int count = 0;
for (int i = 0; i < n; i++)
 for (int j = i+1; j < n; j++)
 if (a[i] + a[j] == 0)
 count++;

Example: 3-SUM

Q. Using \sim notation, how many array accesses as a function of input size n?
A. \sim \frac{1}{2} n^3 array accesses.

int count = 0;
for (int i = 0; i < n; i++)
 for (int j = i+1; j < n; j++)
 for (int k = j+1; k < n; k++)
 if (a[i] + a[j] + a[k] == 0)
 count++;

Bottom line: Use cost model and asymptotic notation to simplify analysis.

Logarithms

Binary Logarithm (\log_2 n)

• The power to which the number 2 must be raised to obtain the value n.
  *x = \log_2 n \iff 2^x = n

• The number of times you need to halve n until you have 1 or fewer left.

Logarithm of Base b (\log_b n)

• The power to which b must be raised to obtain the value n.
  *x = \log_b n \iff b^x = n

• Example: x = \log_{10} 1000 \iff 10^x = 1000 \implies x = 3

Logarithmic Growth

• \log_2(n) is a very slowly growing function.

• When n doubles, \log n increases by 1.

Rapidly Growing Functions

Function Growth Comparison

Common Order of Growth Classifications Table

Practical Implications of Performance

• To sort a million items:

  • On a machine 100 times faster

  • Insertion sort takes 40 minutes

  • Merge sort takes half a second

• Insertion sort O(n^2) ~70 hours,

• Merge sort O(n \log n) ~40 seconds

Approach to Analyzing Loops

• Does the number of times that the loop executes depend on a constant or N?

for (int i=1; i<=100; i++)
 System.out.println(i);

for (int i=1; i<=100; i+=2)
 System.out.println(i);

• Executes 100 times O(1)

• Executes 50 times. It prints every other value. O(1)

Analyzing Loops

• Does the number of times that the loop executes depend on a constant or N?

• If on N, does the loop step increment/decrement by a constant or is it multiplied/divided?

for (int i=1; i<=N; i++)
 System.out.println(i);

for (int i=1; i<=N; i+=2)
 System.out.println(i);

• Executes N times O(n)

• Executes \frac{1}{2} N times. It prints every other value. O(n)

• It doesn’t matter what the constant is. The loop is still O(n)

Analyzing Loops (Multiplication/Division)

• Does the loop step increment/decrement by a constant, or is it multiplied/divided?

for (int i=1; i<= N; i *= 2)
 System.out.print(i + " ");

• Recall: \log_2 n is the power to which the number 2 must be raised to obtain the value n.

• This loop executes \log_2 n times O(\log n)

Analyzing Loops (Different Base Logarithms)

• Does the loop step increment/decrement by a constant, or is it multiplied/divided?

for (int i=1; i<= N; i *= 10)
 System.out.print(i + " ");

• Recall: \log_{10} n is the power to which 10 must be raised to obtain the value n.

• This loop executes \log_{10} n times.

• Logarithms of different bases differ by a constant, so ignore the base for Big-O.

• O(\log n)

Analyzing Code Fragments with Big-O Notation

• Distinguish between statements that count as one step versus N steps.

• N represents the size of the problem, such as array length or a variable N.

• Statements that may not count as one step: loops, function call bodies, string operations.

• Consider single loops: Does the loop depend on a constant or N?

  • Yes: the loop takes constant time.

  • No: determine whether the variable that controls the loop

    • Increases or decreases by a constant (loop is O(N)).

    • Multiplied or divided by a constant (loop is O(log N)).

Analyzing Nested Loops with Big-O Notation

• Determine how many times the innermost statement is executed. *If the loop variables for all of the loops depend on N and increase by a constant, the running time is O(x * n^c)

  • where c is the number of nested loops and x is the execution time of the innermost statement.
    Example:

for (int i=0; i<N; i++)
 for (int j=0; j<N; j++)
 for (int k=0; k<N; k++)
 System.out.println(count++);

for (int i=0; i<N; i++)
 for (int j=i+1; j<N; j++)
 for (int k=j+1; k<N; k++)
 System.out.println(count++);

• O(n^3)

Analyzing Code Fragments with Big-O Notation (Non-Constant Increment)

• If one of the loop variables does not increase/decrease by a constant, total up the sum of the number of times the innermost loop is executed:

for (int i=1; i<=N; i*=2) {
 for (int j=1; j<=i; j++)
 System.out.print(j + " ");
 System.out.println();
}

• 1 + 2 + 4 + 8 + … + N (Geometric Series)

• 2N - 1

• O(N)

Useful Math

Sum of Numbers from 1 to n (Arithmetic Progression)

• Formula to calculate 1 + 2 + 3 + … + (n-2) + (n-1) + n
  *\frac{1}{2} * n * (n+1)

Geometric Series

1 + 2 + 4 + 8 + … + N = 2*n - 1

Doubling Test Calculations

• To determine how the running time changes when N doubles, calculate \frac{f(2n)}{f(n)}.

• To determine how the running time changes when N increases by 1, calculate \frac{f(n+1)}{f(n)}.
  If f(n) = n^2, then \frac{f(2n)}{f(n)} = \frac{(2n)^2}{n^2} = \frac{4n^2}{n^2} = 4
  Hence, when n doubles, the running time quadruples.
  If f(n) = n^3, then \frac{f(2n)}{f(n)} = \frac{(2n)^3}{n^3} = \frac{8n^3}{n^3} = 8
  Hence, when n doubles, the running time increases by a factor of 8.
  If f(n) = 2^n, then \frac{f(n+1)}{f(n)} = \frac{2^{n+1}}{2^n} = 2
  Hence, when n increases by 1, the running time doubles.

Code Analysis Questions

Q-1: What is the order of growth for the running time?
for (int i=1; i<= N; i++)
System.out.println(i);
Answer: C. O(n)

Q-1: What is the order of growth for the running time?
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
System.out.println(i+10 + j);
Answer: D. O(n^2)

Q-1: What is the order of growth for the running time?
for (int i=1; i<= N; i++)
System.out.println(i);
for (int j=1; j<= N; h++)
++count;
Answer: C. O(n)

Q-1: What is the order of growth for the running time?
for (int i = 0; i < N; i = 1*2)
System.out.println(i);
Answer: B. O(log n)

Q-1: What is the order of growth for the running time?
int count = 0;
for (int i = 0; i < n; i++) for (int j=i+1; j < n; j++) for (int k = 1; k <= n; k = k*2) if (a[i] +a[j] >= a[k])
count++;
Answer: D. O(n^2 log n)

Questions about the Code
(i) How many times is the if statement block starting at line 4 executed in terms of n in the worst case? (ii) How many times is the code inside the if statement block starting at line 4 executed in terms of n in the best case? (iii) What is the maximum number of array accesses in terms of n in the worst case? (iv) Use tilde notation to represent the worst-case number of array accesses based on your answer in (iii). (v) Use Big-O notation to represent the order of growth in terms of n, based on the answer in (iv).
Assume a is an integer array and n > 0.
(i) n(n-1)/2 (ii) 0 (iii)6 * n(n-1)/2 = 3n(n-1) = 3n^2 – 3 (iv)~3n^2 (v) O(n^2)

Here are some functions in java with their corresponding worst-case complexities:

Function Worst Case Time
swap O(1)
f0 O(n^2)
f2 O(n)
f3 O(N^2)
f4 O(1)
f5 O(N)
f7 O(log N)
f8 O(log N)
f8b O(n log N
f11 O(log N)