Computational complexity of a nested algorithm

Question

Given an array a [1,2,3,4,5,6,7,8,9,10] let's say we have an algorithm that does the following:

for i in 0..a.length
  for j in 0..a.length
    ...

This would have a Big O runtime of O(n^2) because for each element it will traverse the entire array.

But what if the inner loop only traversed from the outer index forward?

for i in 0..a.length
  for j in i..a.length
    ...

That is, in comparison the first algo will look at n elements each iteration (outer loop). The second algo looks at:

• n elements on the first iteration
• n-1 elements on the second iteration
• n-2 elements on the third iteration
• ...
• 1 element on the last iteration

When calculating Big O runtime for this kind of algo, is it still O(n^2)?

Answer 1

This is still O(n^2). The sum 1 + 2 + ... + n is n(n+1)/2, which is O(n^2).

More generally, for any polynomial function p(n), the sum of p(1) + p(2) + ... + p(n) is O(n p(n)). This proof is a lot harder, since you have to reason about sums of arbitrary powers of n, but it is indeed true. This means, for example, that if you nested a third loop inside out your inner loop that ranged from j to n, the runtime would be O(n^3).