CODEWITHSUNDEEP
mathtime-complexitybig-o
user6562512
user6562512

Reputation:

Run Time Estimate/Big O Notation for Nested For Loop

I'm having trouble understanding the meaning of a function f(x) representing the number of operations performed in some code.

int sum = 0; // + 1
for (int i = 0; i < n; i++)
    for (int j = 1; j <= i; j++)
        sum = sum + 1; // n * (n + 1) / 2

(Please note that there is no 2 in the numerator on that last comment, but there is in the function below.)

Then my notes say that f(x) = 2n(n + 1) / 2 + 1 = O(n^2)

I understand that because there are two for loops, that whatever f(x) is, it will be = O(n^2), but why is the time estimate what it is? How does the j<= i give you n*(n+1)? What about the 2 in the denominator?

Upvotes: 3

Views: 88

Answers (1)

templatetypedef
templatetypedef

Reputation: 373082

Think about, across the entire execution of this code, how many times the inner loop will run. Notice that

  • when i = 0, it runs zero times;
  • when i = 1, it runs one time;
  • when i = 2, it runs two times;
  • when i = 3, it runs three times;
  • ...; and
  • when i = n - 1, it runs n - 1 times.

This means that the total number of times the innermost loop runs is given by

0 + 1 + 2 + 3 + 4 + ... + (n - 1)

This is a famous summation and it solves to

0 + 1 + 2 + 3 + 4 + ... + (n - 1) = n(n - 1) / 2

This is the n - 1st triangular number and it's worth committing this to memory.

The number given - n(n + 1) / 2 - seems to be incorrect, but it's pretty close to the true number. I think they assumed the loop would run 1 + 2 + 3 + ... + n times rather than 0 + 1 + 2 + ... + n - 1 times.

From this it's a bit easier to see where the O(n2) term comes from. Notice that n(n - 1) / 2 = n2 / 2 - n / 2, so in big-O land where we drop constants and low-order terms we're left with n2.

Upvotes: 3

Related Questions