Question

What is the worst-case big-O analysis of the following code fragment?

k = 0;
for (i = 0; i < n; ++i) {for (j = i; j < n; ++j) {
k += n; }
}

Answer 1

The worst-case Big-O analysis of the provided code is O(n^2), as it consists of a nested loop where the inner loop runs on average n/2 times for each iteration of the outer loop.

Step-by-step explanation:

The worst-case Big-O analysis of the given code fragment is O(n^2). The outer loop runs 'n' times, and for each iteration of the outer loop, the inner loop runs for an average of 'n/2' times because it starts from 'i' and goes up to 'n'. The inner operation, 'k += n', is constant time, but occurs within the nested loops. The overall complexity of the nested loops is thus the sum of a series that averages to n*(n/2), which simplifies to (1/2)n^2. Ignoring constants and lower-order terms when discussing Big-O notation, the complexity is O(n^2).