Lab: Order of Growth Experiments

In this lab, you will time several algorithms to determine their growth rates.

Instructions

You should complete this lab individually. Of course, please visit office hours or TA hours if you are having difficulty.

Background

In class, we discussed common runtime growth rates:

• Polynomial: $f(n) = \sum_{i=0}^d a_i n^i$ for constants $a_0, \cdots, a_d$
  • If $a_d > 0$, then f has degree d.
  • Constant functions are 0-degree polynomials.
  • Linear functions are 1-degree polynomials.
  • Quadratic functions are 2-degree polynomials.
  • Cubic functions are 3-degree polynomials.
• Logarithmic: $f(n) = \log_c(n)$ for constant $c$
• Exponential: $f(n) = c^n$ for constant $c$

By plotting input size and runtime, you can experimentally determine an algorithm’s growth rate. For example, this data shows a quadratic growth rate:

It can be difficult to visually differentiate between quadratic, cubic, and exponential functions. To determine the degree of a polynomial runtime, measure the runtime for input size $n$ and $n/2$, which we call $t_n$ and $t_{n/2}$. Then, substitute those times into this equation: $$\text{degree } = \frac{\ln(t_n ÷ t_{n/2})}{\ln(2)}$$ Use the largest input sizes you can measure, to ensure the highest order term overpowers the lower order terms. If the degree is not close to an integer, then the runtime is probably not polynomial.

Measure Algorithm Runtimes

This website includes JavaScript code for several different algorithms. The input size is configured using the text field. You should run each algorithm multiple times, with increasing input sizes. I recommend doubling the input size until the runtime exceeds one minute.

Use this spreadsheet to record and plot algorithm runtimes. I recommend creating a separate sheet for each algorithm.

n=

Run Algorithm A
Run Algorithm B
Run Algorithm C
Run Algorithm D
Run Algorithm E
Run Algorithm F
Run Algorithm G

Submit

Submit your answers on Gradescope. You can resubmit multiple times.

Learning Goals

• Understand common runtime growth rates
• Determine algorithmic growth rates experimentally