What is the asymptotic time-complexity of the following pseudo-code fragment in terms of n For i 1 to n do For j i to n do For k 1 to 3 do Count?

Answer 1

Restating the code fragment in C for clarity:

void f (int n) {

int i, j, k, count = 0;

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

for (j=i; j<n; ++j) {

for (k=0; k<3; ++i {

++count;

}

}

}

printf ("For n=%d, count=%d\n", n, count);

}

If we invoke this algorithm,

f (10);

f (100);

we get the following outputs:

n=10, count=1650

n=100, count=1515000

The relationship between n and count is demonstrably quadratic, thus:

T(n) = Θ(n*n).

10*10 is obviously not 1650 (it is 100) and 100*100 is not 1,616,000 (it is 10,000), however the purpose of time-complexity is merely to give an indication of an algorithm's complexity. If we want to express the time-complexity precisely, it would be:

T(n) = Θ(n*n*(n+1)/2*3)

But if we express time-complexities precisely, it becomes much more difficult to compare algorithms. That is, it is much easier to compare algorithms with time-complexity Θ(n*n) and Θ(log n) than it is to use a more precise notation.

Answer 2

6