Course navigation & on this page
Doubling-ratio experiment
Compare successive timings while repeatedly doubling the 3-SUM input size.
Overview
Compare successive timings while repeatedly doubling the 3-SUM input size. Each trial generates n integers and invokes the cubic ThreeSum counter. The ratio between consecutive timings estimates 2ᵇ for a power-law model anᵇ. The client keeps doubling, so the entire program has no fixed terminating input size.
Step-by-step walkthrough
- Generate a random array for the selected n.
- Start a stopwatch around ThreeSum.count.
- Divide the current elapsed time by the preceding one.
- Double n and repeat.
Complexity analysis
| Best case | Experiment-dependent |
|---|---|
| Average / aggregate | Experiment-dependent |
| Worst case | Θ(n³) per ThreeSum trial |
| Space | Θ(n) generated input |
Each trial generates n integers and invokes the cubic ThreeSum counter. The ratio between consecutive timings estimates 2ᵇ for a power-law model anᵇ. The client keeps doubling, so the entire program has no fixed terminating input size.
A worked example
Times 0.1, 0.8 and 6.4 seconds give ratios near 8, consistent with cubic growth.
A zero or tiny initial timing can yield an unstable ratio. Measurements support a model but do not prove its bound.
Original course code
Source: code/DoublingRatio.java. Original logic, comments, variable names and attribution are retained.
Download DoublingRatio.java/****************************************************************************** * Compilation: javac DoublingRatio.java * Execution: java DoublingRatio * Dependencies: ThreeSum.java Stopwatch.java StdRandom.java StdOut.java * * * % java DoublingRatio * 250 0.0 2.7 * 500 0.0 4.8 * 1000 0.1 6.9 * 2000 0.6 7.7 * 4000 4.5 8.0 * 8000 35.7 8.0 * 4000 3.9 6.6 * ... * ******************************************************************************/ /** * The {@code DoublingRatio} class provides a client for measuring * the running time of a method using a doubling ratio test. * <p> * For additional documentation, see <a href="https://algs4.cs.princeton.edu/14analysis">Section 1.4</a> * of <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */public class DoublingRatio { private static final int MAXIMUM_INTEGER = 1000000; // This class should not be instantiated. private DoublingRatio() { } /** * Returns the amount of time to call {@code ThreeSum.count()} with <em>n</em> * random 6-digit integers. * @param n the number of integers * @return amount of time (in seconds) to call {@code ThreeSum.count()} * with <em>n</em> random 6-digit integers */ public static double timeTrial(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = StdRandom.uniform(-MAXIMUM_INTEGER, MAXIMUM_INTEGER); } Stopwatch timer = new Stopwatch(); ThreeSum.count(a); return timer.elapsedTime(); } /** * Prints table of running times to call {@code ThreeSum.count()} * for arrays of size 250, 500, 1000, 2000, and so forth, along * with ratios of running times between successive array sizes. * * @param args the command-line arguments */ public static void main(String[] args) { double prev = timeTrial(125); for (int n = 250; true; n += n) { double time = timeTrial(n); StdOut.printf("%7d %7.1f %5.1f\n", n, time, time/prev); prev = time; } } }