Big O Notation Calculation

Question

I'm stuck determining the big o notation for the below fragmented code, the given expression is part of I'm trying to figure out. I know given two plain, default for loops results in O(n^2) but the latter is entirely different. Here are the instructions.

The algorithm of

for (j = 0; j < n; j++)
{
  for (k = j; k < n; k++)
  {
  }
}

will result in a number of iterations of given by the expression:

= n + (n-1) + (n-2) + (n-3) + ........ + (n - n)

• Reduce the above series expression to an algebraic expression, without summation.

• After determining the algebraic expression express the performance in Big O Notation.

Answer 1

You can use this method (supposedly applied by Gauss when he was a wee lad).

If you sum all the numbers twice, you have

     1   +   2   +   3   + ... +  n
+    n   + (n-1) + (n-2) + ... +  1
—————————————————————————————————————--
   (n+1) + (n+1) + (n+1) + ... + (n+1)   = n(n+1)

Thus,

1 + 2 + 3 + ... + n = n(n+1)/2

and n(n+1)/2 is (n^2)/2 + n/2, so it is in O(n^2).