Assignment 28 - Complexity Matters

Example Output

Sample Output

Learning Outcomes

  1. Big O Notation
  2. Data Visualization

Goals

The purpose of this assignment is to understand why algorithms are judged by their Big-Oh notations rather than a more precise model, or runtime measurement

Description

Task 1

Using Bridges LineChart object, plot the runtime of an algorithm for problem size ranging from 1 to 105. (Don't use all values of n, take some values in the middle.)

  1. 104 n instructions on a machine at 1 MHz
  2. 5.104 n instructions on a machine at 1MHz
  3. 102 n2 instruction on a machine at 100MHz

Task 2

Using Bridges LineChart object, plot the runtime of an algorithm for problem size ranging from 1 to 104. (Don't use all values of n, take some values in the middle.)

  1. 104 n instructions on a machine at 1 MHz
  2. 102 n2 instructions on a machine at 100MHz
  3. n4 instructions on a machine at 10GHz

Task 3

Using Bridges LineChart object, plot the runtime of an algorithm for problem size ranging from 1 to 102. (Don't use all values of n, take some values in the middle.)

  1. 104 n instructions on a machine at 1 MHz
  2. 102 n2 instructions on a machine at 100MHz
  3. n4 instructions on a machine at 10GHz
  4. 2n instruction on a machine at 1PHz

Conclude

Does it really matter that you can get a slightly faster machine if you can get a lower BigOh complexity? Does it really matter that you can gain a factor of 100 if you can get a lower BigOh complexity?

Extensions

Help

For C++

Bridges documentation LineChart documentation

For Java

Bridges documentation LineChart documentation

For Python

Bridges documentation LineChart documentation