Loop runtime question

algorithm-analysisbig oloopsruntime

I had an exam today and I feel that I did pretty well, except I could not for the life of me figure out what appears to be an unbelievably simple question.

We were asked to give theta notation run times for a few programs(with input size n), and this was one of them:

int sum = 0;
for int i = 0; i < n; i++
   for int j = 0; j < i; j++
      sum++

So I know iterating from 0 to n on both loops would render a O(n²) run time… but with the second loop only iterating to the first loop control variable, I would assume it must be faster… because the second loop never even reaches n iterations until the very last loop-through?

I'm gonna freak out if its O(n²) and I over thought this…

Best Answer

The complexity class is O(n²).

Visual explanation

Imagine a n·n square which lists all the values j takes on. We remove the diagonal (which has n entries) and the upper right half because j will never be larger or equal to i. We are then left with an area of (n² - n)/2.

 i  | values of j     | no of j values
----+-----------------+---------------
 0  | · · · · ·  ⋯  · |  0
 1  | 0 · · · ·  ⋯  · |  1
 2  | 0 1 · · ·  ⋯  · |  2
 3  | 0 1 2 · ·  ⋯  · |  3
 4  | 0 1 2 3 ·  ⋯  · |  4
 :  | : : : :    :  : |  :
n-1 | 0 1 2 3 ⋯ n-2 · | n-1
                       =====
                  SUM: (n² - n)/2

Mathematical explanation

The outer loop executes n times, the inner loop i times. We can write the number of executions of the inner loop body as ∑^m_i=1 i with m = n-1. The sum of all natural numbers up to including m can also be written as m·(m + 1)/2 (the formula for triangular numbers), which leads to n(n-1)/2.

Conclusion

Using either method, we can determine that the nested loops have a complexity of O((n² - n)/2) = O(n²).

Related Solutions

Recursion – How to Determine the Runtime of a Double Recursive Function

You keep on changing your function. But keep picking ones that will run forever without conversion..

Recursion gets complicated, fast. The first step to analyzing a proposed doubly recursive function is to try to trace it through on some sample values, to see what it does. If your calculation gets into an infinite loop, the function is not well defined. If your calculation gets into a spiral that keeps on getting bigger numbers (which happens very easily), it is probably not well defined.

If tracing it through gives an answer, you then try to come up with some pattern or recurrence relation between the answers. Once you have that, you can try to figure out its runtime. Figuring it out can be very, very complicated, but we have results such as the Master theorem that let us figure out the answer in many cases.

Beware that even with single recursion, it is easy to come up with functions whose runtime we do not know how to calculate. For instance consider the following:

def recursive (n):
    if 0 == n%2:
        return 1 + recursive(n/2)
    elif 1 == n:
        return 0
    else:
        return recursive(3*n + 1)

It is currently unknown whether this function is always well-defined, let alone what its runtime is.

Runtime – Modulo Operator Runtime

I assume the review sheet you are reading is flawed:

Modulo/remainder is a O(1) operation (it's essentially just a variation on division, which takes constant time on fixed-sized numbers).
Therefore, the inside of the loop is an O(1) operation,
which makes the total complexity O(√n).

However, let's assume for a moment that % would denote a waste-time-operator with complexity O(log(n)²). In that case, we would end up with a complexity O(√n · log(n)²). The expression √n · log(n)² cannot be simplified. However, the complexity class O(√n · n²) includes O(√n · log(n)²):

   O(√n · n²) includes O(√n · log(n)²)
⇔    √n · n²      >      √n · log(n)²
⇔         n²      >           log(n)²   assuming n ≠ 0
⇔         n       >           log(n)    assuming n > 0
which is true for n > 1

Of the three conditions n ≠ 0, n > 0, n > 1 the last one is the strongest, and is guaranteed by a comment in the code. It would therefore be correct to say that the code has O(√n · n²) complexity, although it is also true that it has O(√n · log(n)²) complexity, which is a stronger statement.

Note that the expression √n · n² can be simplified, but not to n:

   √n · n²
=  n^1/2 · n²
=  n^{1/2 + 2}
=  n^5/2
=  √(n⁵)