Runtime of for loop
for-loop, runtime
Solution
Your question is closely related to the series sum S(k) = 0 + 1 + 2 + ... + (k-2) + (k-1). It can be shown that S(k) = (k*(k-1))/2 = (k*k)/2 - k/2. [How? Reorder the sum as S(k) = {0+(k-1)} + {1+(k-2)} + {2+(k-3)} + .... This shows how.]
Therefore, is the algorithmic order smaller than O(k*k)? Remember that constant coefficients like 1/2 do not influence the big O notation.
Question: So it's equivalent to replacing `j = i+1 to k` with `j = 1 to k`?
Answer: Right. This is tricky, so let's think it through. For `i == 1`, how many times does the inner loop's action run? Answer: it runs `k-1` times. Again, for `i == 2`, how many times does the inner loop's action run? Answer: it runs `k-2` times. Ultimately, for `i == k`, how many times does the inner loop's action run? Answer: it runs zero times. Therefore, over all values of `i`, how many times does the inner loop's action run? Answer: `(k-1) + (k-2) + ... + 0`, which is just the aforementioned sum S(k).
Problem
What's the runtime for this nested for loop in big O notation? ``` for(i = 1 to k) { for(j = i+1 to k) {} } ``` It's smaller than O(k^2) but I can't figure it out.