Question

Analyze the following codes by computing their running time, T(n).

1)

int function ( int n) {

int sum;

for (int i = 0; i < n; i++)

​ sum = sum + (i * n);

return sum;

}

2)

int function(int n) {

​int sum;

​

​for (int i = 0; i < n; i++)

​​if (n < 1000)

​​​sum++;

​​else

​​​sum += function(n);

}

3)

int function(n)

{

​int s = 0;

​for (int i = 1; i <= n*n*n; i++)

​{

​​for (int j = 1; j <= i; j++)

​​{

​​​s = s + j;

​​}

​}

​return s;

}

Answer 1

1)

int function ( int n) {

int sum; // takes O(1) time

for (int i = 0; i < n; i++) // this loop runs n times for i = 0 to n-1

​ sum = sum + (i * n); // this statement is executed n times

return sum; // takes O(1) time

}

Hence, the time complexity of this code snippet is O(n).

2)

int function(int n) {

​int sum; // takes O(1) time

​​for (int i = 0; i < n; i++) // this loop runs n times for i = 0 to n-1

​​if (n < 1000) // takes O(1) time

​​​sum++; // takes O(1) time

​​else

​​​sum += function(n);   // takes O(n) time

}

Hence, the time complexity of the above algorithm is:

= O(n*1000) + O(n * (n-1000))

= O(n²)

3)

int function(n)

{

​int s = 0; // takes O(1) time

​for (int i = 1; i <= n*n*n; i++) // this loop runs n³ times for i = 1 to n³

​{

​​for (int j = 1; j <= i; j++) // this loop runs i times for each i

​​{

​​​s = s + j;

​​}

​}

​return s;

}

Hence, the total number of times the statement ​​​s = s + j; is executed is:

= 1 + 2 + 3 + ..... + n³

= n³(n³ + 1)/2 = O(n⁶)