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 will have OO (n ^ 2) for O (n ^ 2), because for each element it will move throughout the array.

But what if the inner loop only intersects with the outer index ahead?

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

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

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

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

Answer 1

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

In a more general case, for any polynomial function p (n), the sum p (1) + p (2) + ... + p (n) is O (np (n)). This proof is much more complicated, since you have to talk about sums of arbitrary powers of n, but it really is. This means, for example, that if you nested the third loop from your inner loop, which ranged from j to n, the runtime would be O (n ^ 3).

Answer 2

If you are given that a is a specific array, then the time complexity for this algorithm is constant (or O (1)). Maybe I read what you asked too literally, but in order to be as tight as possible O (n ^ 2), a should be an array of the type [1,2, ..., n]. If a clearly has size 10, then the algorithm always works with the same number of steps.

I hope this answer was superfluous, but I am an assistant teacher for a discrete mathematical class, and we often ask rather complex questions that are very similar to this. If I misunderstood the question, then I apologize for wasting your time! Also, the answer that has already been posted is very good!