CODEWITHSUNDEEP
c#big-o
Carlos Rodriguez
Carlos Rodriguez

Reputation: 2220

Big O Analysis for Algorithm

Next in my series of Big O questions that I can't find the answer to

Take the following example

for(int i = 0; i < someNumber; i++)
{
    for(int j = i; j < someNumber; j++)
    {
        DoSomething();
    }
}

Would this still be considered O(n^2)? I only ask because I feel that this has to be less that O(n^2), since the inner loop is executing less and less for every iteration of i (since j is starting closer and closer to someNumber).

Thanks

Upvotes: 3

Views: 141

Answers (1)

Bill the Lizard
Bill the Lizard

Reputation: 405955

The outer loop runs n times. The inner loop starts out running n times, but decreases with each iteration of the outer loop, until the last iteration where it only runs once. The code inside the inner loop will run

n + (n−1) + ... + 2 + 1

times.

That can be simplified to n(n + 1)/2 (proof), or n2/2 + n/2, or finally (n2 + n) / 2. Since the first term is n2, the algorithm is in O(n2).

Upvotes: 16

Related Questions