CODEWITHSUNDEEP
algorithm
Saffor
Saffor

Reputation: 60

What is the running time T(n) of this algorithm?

What is the running time T(n) of a program implementing this algorithm - What is The Total Time ?

T (n) ≈ cop C(n).

sum = 0;
for (i=1; i<=n; i++) 
    for (j=1; j<=i; j++)
        sum++;
for (k=0; k<n; k++) 
    A[k] = k;

Upvotes: 0

Views: 171

Answers (3)

Sandipan Dey
Sandipan Dey

Reputation: 23101

If you want exact analysis, it will be like the following (we need to start from inside out):

enter image description here

where c1, c2 are constants.

Upvotes: 1

user3408531
user3408531

Reputation:

You reach the instruction sum++; n(n+1)/2 times and the instruction A[k]=k; n times.

The total would be T(n)=(n^2+3n)/2.

Upvotes: 1

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186668

Nested loops

  for (i=1; i<=n; i++) 
    for (j=1; j<=i; j++)
      sum++;

brings 

  n           - outer loop
  (n + 1) / 2 - inner loop

  n * (n + 1) / 2 == 0.5 * (n^2 + n) == O(n^2)

operations. You can implement a better O(n) routine:

  sum = n > 0 ? n * (n + 1) / 2 : 0;

  for (k = 0; k < n; k++) 
    A[k] = k;

Upvotes: 4

Related Questions