EECS 281: Data Structures and Algorithms

Section 03 Measuring Runtime Performance

University of Michigan at Ann Arbor

Last Edit Date: 05/11/2023

Disclaimer and Term of Use:

We do not guarantee the accuracy and completeness of the summary content. Some of the course material may not be included, and some of the content in the summary may not be correct. You should use this file properly and legally. We are not responsible for any results from using this file

This personal note is adapted from Professor Marcus Darden and David Paoletti. Please contact us to delete this file if you think your rights have been violated.

This work is licensed under a Creative Commons Attribution 4.0 International License.

Complexity Notation¶

$n$ is the input size
$f(n)$ is the max number of steps when input has size $n$
$O(f(n))$ is the asymptotic upper bound

There are two ways to measure complexity:

Analytically
- Analysis of the code itself
- Recognizing common algorithms / patterns
- Based on a recurrence relation
Empirically
- Measure runtime programmatically
- Measure runtime using external tools
- Test on inputs of a variety of sizes

Note: Programmatically measurements are taken from inside the code itself, which varies greatly depending on the language. Even though in C++, there are many different ways to do it.

Empirical Results

Plot actual run time verses varying input sizes
Include a large range to accurately display trend

Note: For small inputs, asymptotics may not play out yet.

Prediction versus Experiment

What if experimental results are worse than predictions?
- Example: results are exponential when analysis is linear
- Error in complexity analysis
- Error in coding (check for extra loops, unintended operations, etc.)
What if experimental resuts are better than predictions?
- Example: results are linear when analysis is exponential
- Experiment may not have fit worst case scenario
- Error in complexity analysis
- Error in analytical measurements
- Incomplete algorithm implementation
- Algorithm implemented is better then the one analyzed
What if experimental data match asymptotic prediction but runs are too slow?
- Performance bug
- Check compile options
- Look for optimizations to improve the constant factors

Runtime Analysis Tools¶

1. Using a Profiling Tool

This won't tell you the complexity of an algorithm, but it tells you where your program spends its time.
Many different tools exist - in this class we use pref on CAEN to achieve this.

2. Using valgrind

This tool is to check whether our programs have memory leaks.
Who leaked that memory?
- The memory address isn't very useful , we just know that main() called operator new
- Recompile with -g3 instead of -o3 and run valgrind one more time

Analyzing Recursion¶

Iterative functions use loops
A function is recursive if it calls itself

Itrative	Recursive
int power(int x, int n) { int result = 1; for (int i = 0; i ≤ n; ++i) { result = result * x; } return result; }	int power(int x, int n) { if (n == 0) { return 1; } return x * power(x, n - 1); }

For the iterative case, we know that it have $\Theta (n)$ time complexity.

Recurrence Relations

A recurrence relation describes the way a probelm depends on a subproblem.

A recurrence can be written for a computation:

$$ x^n = \begin{equation} \begin{cases} 1&n = 0\\ x\times x^{n-1}&n > 0\\ \end{cases} \end{equation} $$

A recurrence can be written for the time taken:

$$ T(n) = \begin{equation} \begin{cases} c_0&n = 0\\ T(n - 1)+c_1&n > 0\\ \end{cases} \end{equation} $$

A recurrence can be written for the amount of memory used (non-tail recursive):

$$ M(n) = \begin{equation} \begin{cases} c_0&n = 0\\ M(n - 1)+c_1&n > 0\\ \end{cases} \end{equation} $$

Solving Recurrences

Substitution Method
- Write out $T(n)$, $T(n - 1)$, $T(n - 2)$
- Substitute $T(n - 1)$, $T(n - 2)$ into $T(n)$
- Look for a pattern
- Use a summation formula
Master Theorm Method

Example 1 Linear (substitution method):

$ T(n) = \begin{equation} \begin{cases} c_0&n = 0\\ T(n - 1)+c_1&n > 0\\ \end{cases} \end{equation} $

int power(int x, int n) {
    if (n == 0) {
        return 1;
    }
    return x * power(x, n - 1);
}

Step (k)	Recurrence	Subproblem
1	$T(n) = T(n - 1) + c_1$	$T(n - 1) = T(n - 2) + c_1$
2	$T(n) = T(n - 2) + 2c_1$	$T(n - 2) = T(n - 3) + c_1$
3	$T(n) = T(n - 3) + 3c_1$	$T(n - 3) = T(n - 4) + c_1$
...	...	...
k	$T(n) = T(n - k) + kc_1$	$T(n - k) = T(n - k - 1) + c_1$

We now know that $T(n) = T(n - k) + kc_1$.

If $n - k = 0$, we can get $T(0) = c_0$, so in this case, it should be $k = n$. Now we plug this into $T(n) = T(n - k) + kc_1$ and get:

$$T(n) = T(0) + nc_1 = c_0 + nc_1 = O(n)$$

Example 2 Logarithmic (substitution method):

$ T(n) = \begin{equation} \begin{cases} c_0&n = 0\\ T \left(\frac{n}{2}\right)+c_1&n > 0\\ \end{cases} \end{equation} $

int power(int x, int n) {
    if (n == 0) {
        return 1;
    }
    int result = power(x, n / 2);
    result *= result;
    if (n % 2 != 0) {
        result *= x;
    }
    return result;
}

Step (k)	Recurrence	Subproblem
1	$T(n) = T \left(\frac{n}{2}\right)+c_1$	$T\left(\frac{n}{2}\right) = T \left(\frac{n}{4}\right)+c_1$
2	$T(n) = T \left(\frac{n}{4}\right)+2c_1$	$T\left(\frac{n}{4}\right) = T \left(\frac{n}{8}\right)+c_1$
3	$T(n) = T \left(\frac{n}{8}\right)+3c_1$	$T\left(\frac{n}{8}\right) = T \left(\frac{n}{16}\right)+c_1$
...	...	...
k	$T(n) = T \left(\frac{n}{2^k}\right)+kc_1$	$T\left(\frac{n}{2^k}\right) = T \left(\frac{n}{2^{k+1}}\right)+c_1$

We now know that $T(n) = T \left(\frac{n}{2^k}\right)+kc_1$.

If $\frac{n}{2^k} = 1$, we can get $T(1) = T\left(\frac{1}{2}\right) + c_1 = T(0) + c_1 = c_0 + c_1$, so in this case, it should be $n = 2^k \Rightarrow \log_2 n = k$. Now we plug this into $T(n) = T \left(\frac{n}{2^k}\right)+kc_1$ and get:

$$T(n) = T(1) + \log_2 nc_1 = c + \log_2nc_1 = O(\log_2n)$$