1
$\begingroup$

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)

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

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.

$\endgroup$
4
  • $\begingroup$ So you mean the complexity is n^2? $\endgroup$ – motis10 Mar 20 '20 at 18:17
  • $\begingroup$ @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$. $\endgroup$ – Rick Decker Mar 21 '20 at 18:26
  • $\begingroup$ Im not sure I understand you. So the answer is n^2 or nlogn? $\endgroup$ – motis10 Mar 22 '20 at 19:09
  • $\begingroup$ @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)$? $\endgroup$ – Rick Decker Mar 22 '20 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.