This project is to experimentally verify that the expected running time of the randomized selection algorithm is linear.
| Size of Array (n) | T(n) | T(n)/n |
|---|---|---|
| 500 | 2.8e-0.5 | 5.6e-8 |
| 5,000 | 3.2643-4 | 6.526e-8 |
| 10,000 | 2.32e-4 | 2.328e-8 |
| 12,000 | 3.36e-4 | 2.24e-8 |
| 15,000 | 3.36e-4 | 2.24e-8 |
| 25,000 | 3.18e-4 | 1.27e-8 |
| 50,000 | 7.78e-4 | 1.556e-8 |
To determine if the running time is linear, take the average of the running times you get for each array size and divide by the size of the array.
Change the size of your array and compare times :)