# Thread: Running time analysis

1. ## Running time analysis

Code:
```sum=0;
for (i=1; i<=n; i*=2)
for (j=1; j<=i; j++)
sum++;

r=0
for(i=1; i<= n ; i++)
for (j = 1; j <= n; j*=2)
if (n mod 2 == 0) // n even
for (k = 1; k <= n; k++)
r++;
else // n odd
r--;```
how to calculate the running analysis for the worst case of the two above algorithms??

2. Please change your [\code] tag - replace the \ with /, and it will show your code correctly.

3. Code:
```sum=0;
for (i=1; i<=n; i*=2)
for (j=1; j<=i; j++)
sum++;

r=0
for(i=1; i<= n ; i++)
for (j = 1; j <= n; j*=2)
if (n mod 2 == 0) // n even
for (k = 1; k <= n; k++)
r++;
else // n odd
r--;```
good point

4. Ok... you found the code tags... now learn how to indent your code...

Indent style - Wikipedia, the free encyclopedia

5. This should do the trick:

Code:
```clock_t t0, t1, elapsed;
t0 = clock();
/* Code to clock goes here */
t1 = clock();
elapsed = 1000 * (t1 - t0) / (CLOCKS_PER_SEC);
printf("Avg elapsed time: %ld ms\n\n", elapsed/MAX_LOOPS);```

6. How can i analyze the time that needs the program to be executed? is it all about maths?

7. Originally Posted by antros48
How can i analyze the time that needs the program to be executed? is it all about maths?
Do you mean that you want to estimate how long it will take to run in advance?

8. Originally Posted by antros48
How can i analyze the time that needs the program to be executed? is it all about maths?
Are you talking about the run time complexity of those snippets of code? Then yes, it is more or less about counting and maths. Go through the algorithm with specific input to understand what is happening. Count to give yourself a ballpark estimate of how the number of operations might vary with the size of the input, if only for the average case at first.

Since this is not about C, I am moving this thread.

9. In the first example you have a loop of order n, and within this loop is another loop of order n (it loops to i, which itself is order n), making the total O(n^2).

In the second example you have a loop of order n, and within this loop another loop of order n, and within THAT loop, you get ANOTHER loop of order n, every other time, which makes the whole thing O(n^3).

10. Code:
`for (i=1; i<=n; i*=2)`
Is this really a loop of order n, and not perhaps of log(n)?

Popular pages Recent additions