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)?

Wooble · Accepted Answer · 2012-06-14 17:41:38Z

10

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).

edited Jun 14, 2012 at 17:41

Wooble

90.6k12 gold badges111 silver badges132 bronze badges

answered Jun 14, 2012 at 17:35

templatetypedef

376k112 gold badges954 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Dylan M. · Accepted Answer · 2012-06-14 21:30:32Z

0

If you are given that a is that specific array, then the time complexity for that algorithm is constant (or O(1)). Maybe I read what you asked too literally, but for the tightest bound to be O(n^2), a would have to be an array like [1,2,...,n]. If a is explicitly size 10, then, the algorithm always runs in the same number of steps.

Hopefully, this answer was unnecessary, but I'm a teaching assistant for a discrete math class, and we give trick questions pretty frequently that are very similar to this. If I misunderstood the question, then I apologize for wasting your time! Also, the answer that was already posted is very good!

answered Jun 14, 2012 at 21:30

Dylan M.

1161 silver badge7 bronze badges

Collectives™ on Stack Overflow

Computational complexity of a nested algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related