6 Replies - 592 Views - Last Post: 27 September 2012 - 04:42 PM Rate Topic: -----

#1 oha055  Icon User is offline

  • D.I.C Regular

Reputation: 48
  • View blog
  • Posts: 250
  • Joined: 02-February 09

Calculate running time for small algorithm

Posted 27 September 2012 - 05:42 AM

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


Is This A Good Question/Topic? 0
  • +

Replies To: Calculate running time for small algorithm

#2 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8324
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Calculate running time for small algorithm

Posted 27 September 2012 - 05:56 AM

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
Was This Post Helpful? 2
  • +
  • -

#3 farrell2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 822
  • View blog
  • Posts: 2,529
  • Joined: 29-July 11

Re: Calculate running time for small algorithm

Posted 27 September 2012 - 06:35 AM

View Postpbl, 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.
Was This Post Helpful? 0
  • +
  • -

#4 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8324
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Calculate running time for small algorithm

Posted 27 September 2012 - 11:08 AM

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 :)
Was This Post Helpful? 0
  • +
  • -

#5 Kakerergodt  Icon User is offline

  • D.I.C Head

Reputation: 87
  • View blog
  • Posts: 201
  • Joined: 01-May 12

Re: Calculate running time for small algorithm

Posted 27 September 2012 - 12:14 PM

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

Was This Post Helpful? 1
  • +
  • -

#6 farrell2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 822
  • View blog
  • Posts: 2,529
  • Joined: 29-July 11

Re: Calculate running time for small algorithm

Posted 27 September 2012 - 01:46 PM

View Postpbl, 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.
Was This Post Helpful? 1
  • +
  • -

#7 oha055  Icon User is offline

  • D.I.C Regular

Reputation: 48
  • View blog
  • Posts: 250
  • Joined: 02-February 09

Re: Calculate running time for small algorithm

Posted 27 September 2012 - 04:42 PM

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 :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1