# Sum of sequence complexity

I try to find out what is the time complexity of this program:

for (int i =0; i < n; i++)
{
for (int j = i+1; j < n; j++)
{
//Do something O(1)
}
}


I tried to find any explanation, As I see, it something like Arithmetic progression sum (n(n-1)/2).

Is it? or it's just O(n^2)

• Since $n$ is constant, your program runs in $O(1)$. – Yuval Filmus Mar 20 '20 at 22:33
• I meant n is unknown. if it's just n? (I update the question) – motis10 Mar 21 '20 at 8:18

The inner loop will iterate once with $$j=i+1$$, once again with $$j=i+2$$, and so on, up to the last iteration with $$j=n-1$$, so there will be, for each $$i$$ in the outer loop, $$(i+1)-(n-1)-1=n+i-1$$ time contributions from the inner loop. Add these to get your answer.
• @motis10 Kinda. In fact, you can show that if the "//Do something O(1)" is interpreted as "1" then the complexity is $n(n-1)/2$. – Rick Decker Mar 21 '20 at 18:26
• @motis10 Let's see: the actual complexity is $n(n-1)/2$ that is $\frac{1}{2}n^2-\frac{1}{2}n$. Is that $O(n^2)$ or $O(n\log n)$? – Rick Decker Mar 22 '20 at 21:09