DSACommunity question

Complexity when inner loop starts from i

Asked by Abhishek Dubey 2 months ago 2 answers 7 votes

for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
        count++;

Answer was O(n^2). But the inner loop runs fewer times every iteration so shouldn't it be less? Confused

2 answers

Arjun Mehta2 months agoMost voted8

Count it: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2

That's about n²/2. Big O drops the 1/2, so still O(n²). It is half the work, just not a different growth rate.

It only gets smaller if the inner loop shrinks multiplicatively, like j *= 2, that gives log n.

Abhishek Dubey2 months ago

got it thanks

Structured lessons on DSA, core CS, Java and interview skills, each ending in a quiz so you know it stuck.