The doubling ratio experiment program generates a sequence of random arrays, doubling the array size at each step. It starts with an array of size 250. The next array is of size 500, the next one 1000 etc. Each array serves as an input to one of the three procedures: ThreeSum, TwoSum, FourSum, or TwoEqual. The program measures the running times for each input size. It also calculates the ratio of each running time with the previous.

```using System;
using System.Diagnostics;

namespace ConsoleTest
{
class Program
{
private static Stopwatch stopwatch = new Stopwatch();
private static Random rnd = new Random();

static void Main(string[] args)
{
double prev = RunTimeTrial(125);
for (int N = 250; true; N += N)
{
double time = RunTimeTrial(N);
Console.WriteLine("Size: {0}   Elapsed time: {1:F2} sec   Ratio: {2:F2}", N, stopwatch.ElapsedMilliseconds / 1000.0, time / prev);
prev = time;
}
}

static double RunTimeTrial(int N)
{
// Generate N random 6-digit numbers.
const int MAX = 999999;
int[] a = new int[N];

for (int i = 0; i < N; ++i)
a[i] = rnd.Next(-MAX, MAX + 1);

stopwatch.Reset();
stopwatch.Start();

//int cnt = RunThreeSum(a);
//int cnt = RunTwoSum(a);
//int cnt = RunFourSum(a);
int cnt = RunTwoEqual(a);

return (stopwatch.ElapsedMilliseconds / 1000.0);
}

// Count triples that sum to 0.
static int RunThreeSum(int[] a)
{
int N = a.Length;
int cnt = 0;

for (int i = 0; i < N; ++i)
for (int j = i + 1; j < N; ++j)
for (int k = j + 1; k < N; ++k)
if (a[i] + a[j] + a[k] == 0)
cnt++;
return cnt;
}

// Count pairs that sum to 0.
static int RunTwoSum(int[] a)
{
int N = a.Length;
int cnt = 0;

for (int i = 0; i < N; ++i)
for (int j = i + 1; j < N; ++j)
if (a[i] + a[j] == 0)
cnt++;
return cnt;
}

// Determine the number of pairs of values that are equal.
// This is a quadratic solution.
static int RunTwoEqual(int[] a)
{
int N = a.Length;
int cnt = 0;

for (int i = 0; i < N; ++i)
for (int j = i + 1; j < N; ++j)
if (a[i] == a[j])
cnt++;
return cnt;
}

// Count quadruplets that sum to 0.
// The order of growth is quartic.
static int RunFourSum(int[] a)
{
int N = a.Length;
int cnt = 0;

for (int i = 0; i < N; ++i)
for (int j = i + 1; j < N; ++j)
for (int k = j + 1; k < N; ++k)
for (int l = k + 1; l < N; ++l)
if (a[i] + a[j] + a[k] + a[l] == 0)
cnt++;
return cnt;
}
}
}
```

The procedures yield the following outputs:

ThreeSum - the order of growth is N3; to predict running times, multiply the last observed running time by 2b = 23 = 8

```Size: 250   Elapsed time: 0.01 sec   Ratio: 11.00
Size: 500   Elapsed time: 0.08 sec   Ratio: 7.18
Size: 1000   Elapsed time: 0.58 sec   Ratio: 7.35
Size: 2000   Elapsed time: 4.43 sec   Ratio: 7.62
Size: 4000   Elapsed time: 33.62 sec   Ratio: 7.59
Size: 8000   Elapsed time: 269.00 sec   Ratio: 8.00
Size: 16000   Elapsed time: 2144.69 sec   Ratio: 7.97
```

TwoSum - the order of growth is N2; to predict running times, multiply the last observed running time by 2b = 22 = 4

```Size: 250   Elapsed time: 0.00 sec   Ratio: NaN
Size: 500   Elapsed time: 0.00 sec   Ratio: NaN
Size: 1000   Elapsed time: 0.00 sec   Ratio: 8
Size: 2000   Elapsed time: 0.01 sec   Ratio: 4.00
Size: 4000   Elapsed time: 0.03 sec   Ratio: 3.38
Size: 8000   Elapsed time: 0.11 sec   Ratio: 3.96
Size: 16000   Elapsed time: 0.36 sec   Ratio: 3.36
Size: 32000   Elapsed time: 1.57 sec   Ratio: 4.38
Size: 64000   Elapsed time: 5.58 sec   Ratio: 3.55
Size: 128000   Elapsed time: 22.24 sec   Ratio: 3.99
Size: 256000   Elapsed time: 89.86 sec   Ratio: 4.04
Size: 512000   Elapsed time: 356.99 sec   Ratio: 3.97
Size: 1024000   Elapsed time: 1420.49 sec   Ratio: 3.98```

FourSum - the order of growth is N4; to predict running times, multiply the last observed running time by 2b = 24 = 16

```Size: 250   Elapsed time: 0.73 sec   Ratio: 13.70
Size: 500   Elapsed time: 10.27 sec   Ratio: 14.14
Size: 1000   Elapsed time: 157.90 sec   Ratio: 15.38
Size: 2000   Elapsed time: 2461.19 sec   Ratio: 15.59```

TwoEqual - the order of growth is N2; to predict running times, multiply the last observed running time by 2b = 22 = 4

```Size: 250   Elapsed time: 0.00 sec   Ratio: NaN
Size: 500   Elapsed time: 0.00 sec   Ratio: NaN
Size: 1000   Elapsed time: 0.00 sec   Ratio: 8
Size: 2000   Elapsed time: 0.01 sec   Ratio: 4.00
Size: 4000   Elapsed time: 0.03 sec   Ratio: 4.25
Size: 8000   Elapsed time: 0.10 sec   Ratio: 3.06
Size: 16000   Elapsed time: 0.40 sec   Ratio: 3.87
Size: 32000   Elapsed time: 1.42 sec   Ratio: 3.53
Size: 64000   Elapsed time: 5.54 sec   Ratio: 3.90
Size: 128000   Elapsed time: 22.49 sec   Ratio: 4.06
Size: 256000   Elapsed time: 90.50 sec   Ratio: 4.02
Size: 512000   Elapsed time: 362.00 sec   Ratio: 4.00 ```

The doubling ratio experiment can be used to determine the approximate order of growth of the running time of a program. Note that the above ratios approach a limit 2b where b is a positive integer. We can conclude from that that the order of growth of the running time is approximately Nb where N is the size of the input array. To predict running times, simply multiply the last observed running time by 2b.

We can achieve better performance by providing a sorted array as input. Below, there are re-worked TwoSum and ThreeSum procedures. The TwoSum procedure uses a linear algorithm while the ThreeSum procedure uses a quadratic algorithm:

```using System;
using System.Diagnostics;

namespace ConsoleTest
{
class Program
{
private static Stopwatch stopwatch = new Stopwatch();
private static Random rnd = new Random();

static void Main(string[] args)
{
double prev = RunTimeTrial(125);
for (int N = 250; true; N += N)
{
double time = RunTimeTrial(N);
Console.WriteLine("Size: {0}   Elapsed time: {1:F2} sec   Ratio: {2:F2}", N, stopwatch.ElapsedMilliseconds / 1000.0, time / prev);
prev = time;
}
}

static double RunTimeTrial(int N)
{
// Generate N random 6-digit numbers.
const int MAX = 999999;
int[] a = new int[N];

for (int i = 0; i < N; ++i)
a[i] = rnd.Next(-MAX, MAX + 1);

// Sort the array.
Array.Sort(a);

stopwatch.Reset();
stopwatch.Start();

int cnt = RunThreeSumFaster(a);
//int cnt = RunTwoSumFaster(a);

return (stopwatch.ElapsedMilliseconds / 1000.0);
}

// Count triples that sum to 0.
// RunThreeSumFaster uses a quadratic algorithm to count triples
// that sum to zero after the array is sorted.
static int RunThreeSumFaster(int[] a)
{
int cnt = 0;

for (int i = 0; i < a.Length; ++i)
{
int j = i + 1;
int k = a.Length - 1;

while (j < k)
{
if (a[i] + a[j] + a[k] == 0)
{
cnt++;
j++;
k--;
}

if (a[i] + a[j] + a[k] < 0)
{
j++;
}
else if (a[i] + a[j] + a[k] > 0)
{
k--;
}
}
}

return cnt;
}

// Count pairs that sum to 0.
// RunTwoSumFaster uses a linear algorithm to count pairs
// that sum to zero after the array is sorted.
static int RunTwoSumFaster(int[] a)
{
int cnt = 0;
int i = 0;
int j = a.Length - 1;

while (a[i] < 0 && a[j] > 0)
{
if (a[i] + a[j] == 0)
{
cnt++;
i++;
j--;
}

if (Math.Abs(a[i]) < a[j])
{
j--;
}
else if (Math.Abs(a[i]) > a[j])
{
i++;
}
}

return cnt;
}
}
}
```