CODEWITHSUNDEEP
c#for-looptime
Naser.Sadeghi
Naser.Sadeghi

Reputation: 1302

Calculating the approximate run time of a for loop

I have a piece of code in my C# Windows Form Application that looks like below:

List<string> RESULT_LIST = new List<string>();
int[] arr = My_LIST.ToArray();

string s = "";

Stopwatch sw = new Stopwatch();
sw.Start();

for (int i = 0; i < arr.Length; i++)
{
  int counter = i;
  for (int j = 1; j <= arr.Length; j++)
  {
    counter++;
    if (counter == arr.Length)
    {
      counter = 0;
    }
    s += arr[counter].ToString();
    RESULT_LIST.Add(s);
  }
  s = "";
}
sw.Stop();
TimeSpan ts = sw.Elapsed;
string elapsedTime = String.Format("{0:00}", ts.TotalMilliseconds * 1000);
MessageBox.Show(elapsedTime);

I use this code to get any combination of the numbers of My list. I have behaved with My_LIST like a recursive one. The image below demonstrates my purpose very clearly:

enter image description here

All I need to do is:

Making a formula to calculate the approximate run time of these two nested for loops to guess the run time for any length and help the user know the approximate time that he/she must wait.

I have used a C# Stopwatch like this: Stopwatch sw = new Stopwatch(); to show the run time and below are the results(Note that in order to reduce the chance of error I've repeated the calculation three times for each length and the numbers show the time in nano seconds for the first, second and third attempt respectively.):

  1. arr.Length = 400; 127838 - 107251 - 100898
  2. arr.Length = 800; 751282 - 750574 - 739869
  3. arr.Length = 1200; 2320517 - 2136107 - 2146099
  4. arr.Length = 2000; 8502631 - 7554743 - 7635173

Note that there are only one-digit numbers in My_LIST to make the time of adding numbers to the list approximately equal.

How can I find out the relation between arr.Length and run time?

Upvotes: 1

Views: 784

Answers (3)

Adam Brown
Adam Brown

Reputation: 1729

Don't assume the algorithm is necessarily N^2 in time complexity.

Take the averages of your numbers, and plot the best fit on a log-log plot, then measure the gradient. This will give you an idea as to the largest term in the polynomial. (see wikipedia log-log plot)

Once you have that, you can do a least-squares regression to work out the coefficients of the polynomial of the correct order. This will allow an estimate from the data, of the time taken for an unseen problem.

Note: As Eric Lippert said, it depends on what you want to measure - averaging may not be appropriate depending on your use case - the first run time might be more correct.

This method will work for any polynomial algorithm. It will also tell you if the algorithm is polynomial (non-polynomial running times will not give straight lines on the log-log plot).

Upvotes: 1

Eric Lippert
Eric Lippert

Reputation: 660148

First, let's suppose you have examined the algorithm and noticed that it appears to be quadratic in the array length. This suggests to us that the time taken to run should be a function of the form

t = A + B n + C n2

You've gathered some observations by running the code multiple times with different values for n and measuring t. That's a good approach.

The question now is: what are the best values for A, B and C such that they match your observations closely?

This problem can be solved in a variety of ways; I would suggest to you that the least-squares method of regression would be the place to start, and see if you get good results. There's a page on it here:

www.efunda.com/math/leastsquares/lstsqr2dcurve.cfm

UPDATE: I just looked at your algorithm again and realized it is cubic because you have a quadratic string concat in the inner loop. So this technique might not work so well. I suggest you use StringBuilder to make your algorithm quadratic.

Now, suppose you did not know ahead of time that the problem was quadratic. How would you determine the formula then? A good start would be to graph your points on log scale paper; if they roughly form a straight line then the slope of the line gives you a clue as to the power of the polynomial. If they don't form a straight line -- well, cross that bridge when you come to it.

Upvotes: 5

Steve
Steve

Reputation: 11963

Well you gonna do some math here.

Since the total number of runs is exactly n^2, not O(n^2) but exactly n^2 times.

Then what you could do is to keep a counter variable for the number of items processed and use math to find out an estimate

int numItemProcessed;
int timeElapsed;//read from stop watch
int totalItems = n * n;

int remainingEstimate = ((float) totalItems - numItemProcessed) / numItemProcessed) * timeElapsed

Upvotes: 2

Related Questions