Write GrowthTable with four methods that count how many times their innermost statement runs:
halving(n):for (i = n; i >= 1; i /= 2);linearithmic(n): a loop of n iterations around the halving loop;triangular(n):for i in 0..n-1, for j in i+1..n-1;cubic(n): three nested loops of n.
Read n and a number of rows; print one row per size, doubling n each time, and finally by what factor the last doubling multiplied the n²/2 and n³ counts.
For the input
10 4
the program prints
n log n log n n^2/2 n^3
10 4 40 45 1000
20 5 100 190 8000
40 6 240 780 64000
80 7 560 3160 512000
Doubling n multiplied n^2/2 by 4.05 and n^3 by 8.00