Thread: big O notation

I am working on this algorithm and I am supposed to select a notation for the number of times the statement x = x + 1 is executed in the algorithm:

Code:

for i = 1 to n
  for j = 1 to n
    for k = 1 to i

  x = x + 1

if each integer 1 + 2 + ... n <= n + n + ... n = n * n * n = n^3 for all n >= 1.

it follows that

1 + 2 + ... n = O(n^3)


My question here is did I explain myself correctly to get O(n^3)?

No. For each i, the two inner loops take 1 + 2 + ... n (n terms) <= n + n + ... n (n terms) = n^2. However, the inner loops are run for each i from 1 to n.

I assume that the body of the innermost loop consisted of x = x + 1. As it is, the indentation may suggest that the innermost loop is empty and the assignment is done in the outermost loop.

Originally Posted by emakarov

No. For each i, the two inner loops take 1 + 2 + ... n (n terms) <= n + n + ... n (n terms) = n^2. However, the inner loops are run for each i from 1 to n.

It is desirable to actually sum rather than bound it this way so that we know that the smallest integer such that we can write is

CB