Consider:
<code class="language-java">int s = 0; for (int i = 0; i < n; i++) for (int j = i; j < n; j++) for (int k = 0; k < j; k++) s++; </code></pre> What is the worst-case time complexity in terms of n?
- A
O(n^2 log n)
- B
O(n^2)
- C
O(n log n)
- Dcheck_circle
O(n^3)
Explanation
The outer loop runs n times; the middle loop runs up to n times; the inner loop runs up to n times. Although the bounds depend on i and j, the triple nesting yields a sum proportional to n^3 / 6, which is O(n^3).