[oha055]

So I have got this assignment to calculate the running time (using Tilde approximation) of this small piece of code and I can't seem to figure it out.

	int f2(int n) {
		int sum = 0;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < i*i; j++)
				sum++;
		return sum;
	}

An easier example would be this piece:

	f1(int n) {
		int sum = 0;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				sum++;
		return sum;
	}

Which, has a running time of N * N (or N^2), because for each time the outer for-loop increments, the inner for-loop is run N times. Example: if n = 10, then the variable sum will be incremented 10^2 times.

I am not asking for the answer, I am just hoping that someone can nudge me in the right direction, because I really can't seem to wrap my head around it right now.

Thanks

This post has been edited by oha055: 27 September 2012 - 05:43 AM

[pbl]

The closest evaluation you can have is with System.nanoTime() but you will have to call your method a few million times to get a significant value

   long start = System.nanoTime();
   for(int i = 0; i < 1000000; ++i) 
        f2(1000);
   long now = System.nanoTime();
   long delta = (now - start) / 1000000;

delat will be your time in nano for f2 called with a value of 1000

[farrell2k]

pbl, on 27 September 2012 - 12:56 PM, said:

The closest evaluation you can have is with System.nanoTime() but you will have to call your method a few million times to get a significant value

   long start = System.nanoTime();
   for(int i = 0; i < 1000000; ++i) 
        f2(1000);
   long now = System.nanoTime();
   long delta = (now - start) / 1000000;

delat will be your time in nano for f2 called with a value of 1000

Divide by 1,000,000,000 for nanotime.

[pbl]

Divide delta by 1,000,000 to get the time of one execution in nano
and has farrell2k said then by 1,000,000,000 to get it in seconds but I doubt a method call will last a second

[Kakerergodt]

I assume you're gonna find a mathematical equation for the number of times "sum" is increased, and not the actual time?

If so, the series are as follows:

0^2, 1^2, 2^2, 3^2, 4^2,... (n-1)^2

..you can now sum them all together. (Remember though that your last number is 'n-1' and not 'n').


Edit: This might help link.

This post has been edited by Kakerergodt: 27 September 2012 - 12:26 PM

[farrell2k]

pbl, on 27 September 2012 - 06:08 PM, said:

Divide delta by 1,000,000 to get the time of one execution in nano
and has farrell2k said then by 1,000,000,000 to get it in seconds but I doubt a method call will last a second

too many zeros makes one confused. You're probably going to have to go / 10,000 for anything meaningful.

[oha055]

Thanks guys!

Yes, the assignment was to find a mathematical approximation of the running time. I got it now! You have been of great help, as always