Your question is closely related to the sum of the series 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? We reorder the sum as S (k) = {0+ (k-1)} + {1+ (k-2)} + {2+ (k-3)} + .... This shows how.]
Consequently, the algorithmic order is less than O (k * k)? Remember that constant coefficients, such as 1/2, do not affect the large O notation.
Question: So, is this equivalent to replacing j = i+1 to k with j = 1 to k ?
Answer: Right. It's hard, so think about it. For i == 1 , how many times does the inner loop action execute? Answer: it starts k-1 times. Again, for i == 2 , how many times does the action of the inner loop execute? Answer: it starts k-2 times. Ultimately, for i == k , how many times does the inner loop action execute? Answer: it works zero time. Therefore, in all values of i , how many times is the action of the inner loop performed? Answer: (k-1) + (k-2) + ... + 0 , which is only the above sum S (k).