# Calculate running time for small algorithm

Page 1 of 1

## 6 Replies - 1304 Views - Last Post: 27 September 2012 - 04:42 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=293385&amp;s=6a499b39ae9da9063510e0fb24f6c3c2&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 oha055

• D.I.C Regular

Reputation: 49
• Posts: 273
• 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

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

Reputation: 8370
• Posts: 31,956
• 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

### #3 farrell2k

• D.I.C Lover

Reputation: 875
• Posts: 2,706
• Joined: 29-July 11

## Re: Calculate running time for small algorithm

Posted 27 September 2012 - 06:35 AM

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.

### #4 pbl

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

Reputation: 8370
• Posts: 31,956
• 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

### #5 Kakerergodt

Reputation: 89
• 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').

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

### #6 farrell2k

• D.I.C Lover

Reputation: 875
• Posts: 2,706
• Joined: 29-July 11

## Re: Calculate running time for small algorithm

Posted 27 September 2012 - 01:46 PM

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.

### #7 oha055

• D.I.C Regular

Reputation: 49
• Posts: 273
• 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