Answer:
O(n2)
Step-by-step explanation:
the first iteration algorithm of the i-for loop (the outer loop), the j-for loop (the inner loop) will run 2 to
n times which is represented as
(n − 1 times).
the second iteration algorithm of the i-for loop, the j-for loop will run 3 to n times represented as
(n − 2 times).
the third to the last iteration algorithm of the i-for loop, the j-for loop will run n − 1 to n times (2 times).
And the second to the last iteration of the i-for loop, the j-for loop will run from n to n times (1 time)
For the last iteration of the i-for loop, the j-for loop will run 0 times because i + 1 > n.
Now we know that the number of times the loops are run is
1 + 2 + 3 + . . . + (n − 2) + (n − 1) = n(n − 1)/2
So we can express the number of total iterations as n(n − 1)/2.
Since we have two operations per loop (one comparison and one multiplication), we have
2 ·n(n−1)/2 = n
2 − n operations.
So f(n) = n2 − n
f(n) ≤ n2
for n > 1.
Therefore, the algorithm is O(n2) with
C = 1 and k = 1.
