Algorithms – Run Time of Nested While Loop Inside For Loop

algorithms

I'm here to clarify my understanding of the run times of these 2 algorithms:

Algorithm1(n):
For i = 1 to n
    j = 1
    while i+j < n
        j = j+1

and

Algorithm2(n):
For i = 1 to n
    j = 1
    while i*j < n
        j = j+1

The first algorithm I believe is O(n) because the inner loop is bounded by n, and the while condition is incremented linearly as i is incremented by the outer for loop. Otherwise, I would say O(n^2) if I'm wrong.

The second algorithm I believe is O(log(n^2)) because, as i increases, the amount of iterations will decrease in the while loop which is controlled by the outer for loop.

Best Answer

Your first algorithm is O(n^2), as the outer loop executes n times, and on average the inner loop executes n/2 times; we discard the constant factor as we only care about asymptotic behavior.

Your second algorithm is I believe O(n log n): the outer loop again executes n times, so there must be a factor of n in the answer, and I believe the inner loop executes log n times on average.

Note that your suggested answer of O(log (n^2)) is not a valid answer in any case: log (n^2) = 2 log n, so O(log (n^2)) should be simplified to O(log n).

Background

For an arbitrary for loop such as:
```
for (int p = …; …)
    do_something(p);
```
it should be clear that the run time of this loop is simply the sum of the run times of the inner computations (i.e. do_something(p) in this case). Note that the run time of the inner computation may depend on the loop variable(s).

In the special case where the run time of do_something(p) is independent of the loop variable(s), the run-time is then proportional to the number of times the inner computation is executed.
Typically, simple arithmetic such as incrementing (sum++) are constant-time operations.
For brevity I will use log to denote the base-2 logarithm. Additionally, I will use pow(x, y) to denote x raised to the power y because ^ is often used for something else in the C-family of languages.

The problems

The interesting coincidence in this set of problems is that the run time of each computation is actually proportional to the final value of the sum (can you see why?) so the question can be simplified to: how does the final value of sum vary with the parameter N?

The sum can be calculated algebraically, but we don't need to know the exact result. We just need to make some good estimates.

Problem A

int sum = 0;
for (int n = N; n > 0; n /= 2)
  for (int i = 0; i < n; i++)
    sum++;

How many times does the outer loop run? It starts at N and goes down by half each time until it hits zero. This is just (a discrete version of) an exponential decay with a base of 2. Therefore, we can make an educated guess that

n ∝ 1 / pow(2, p)    [approximately]

Here, we define p to be a counter that increases by 1 each time the outer loop is repeated. In fact, this is exactly what your graph plots.

Where does p start? We can just pick p_start = 0 for convenience, and this allows us to determine the coefficient of proportionality:

 n ≈ N / pow(2, p)

Where does p end? Whenever n reaches zero! Since this is integer division, n can only be zero if N < pow(2, p). From this we can deduce that p_end ≈ log(N) (base-2 logarithm). With experience, you can easily skip this entire analysis and jump straight to this conclusion instead.

Now we can rewrite the loop using the variable p instead of n (again, approximately). Notice that every instance of n must be substituted:

int sum = 0;
for (int p = 0; p < log(N); p++)
  for (int i = 0; i < N / pow(2, p); i++)
    sum++;

The advantage of writing the loop like this is that it becomes obvious how many times the outer loop is repeated. (Keen readers may notice that this is

The inner loop consists of only increments to sum and is repeated N / pow(2, p) times, so we can just rewrite the above to:

int sum = 0;
for (int p = 0; p < log(N); p++)
  sum += N / pow(2, p);

(Note that the run time of this loop may no longer be the same, but the value of sum still reflects the run time of the original problem.)

From this code we can write the value of sum as:

$sum ≈ ∑[p = 0 to log(N)] (N / pow(2, p))$

(As randomA noted, this is just a geometric series so there is a well-known closed-form expression for the sum. Here I use a more general technique based on calculus, however.)

This can be simplified further by approximating the summation as an integral:

$sum ≈ ∫[0 to log(N)] (N / pow(2, p)) dp ≈ N / ln(2)$

And there you go, the run time of the problem A is linear with respect to N.

Problem B

int sum = 0;
for (int i = 1; i < N; i *= 2)
  for (int j = 0; j < i; j++)
    sum++;

The problem here is similar, but I'll omit some of the steps. The variable i grows exponentially, so we can do the transformation:

i ≡ pow(2, p)

with p increasing by one at each iteration, starting from 0, and ending at log(N). After variable substitution, the loop becomes:

int sum = 0;
for (int p = 0; p < log(N); p++)
  for (int j = 0; j < pow(2, p); j++)
    sum++;

which reduces to:

int sum = 0;
for (int p = 0; p < log(N); p++)
  sum += pow(2, p);

You can apply the same tricks again to find a closed-form expression for the sum: it is also O(N).

Problem C

int sum = 0;
for (int i = 1; i < N; i *= 2)
  for (int j = 0; j < N; j++)
    sum++;

This one is actually quite a bit easier because the number of repeats of the inner loop doesn't depend on the outer loop variable, so we can go right away and simplify this to:

int sum = 0;
for (int i = 1; i < N; i *= 2)
  sum += N;

The loop has the same exponential behavior as in Problem B, so it is run only log(N) times, so this can then be simplified to:

int sum = 0;
sum += log(N) * N;

Hence, the run time is O(N log(N)).

Algorithm Big O – Growth Rate of (n^2 + n) / 2

When calculating the Big-O complexity of an algorithm, the thing being shown is the factor that gives the largest contribution to the increase in execution time if the number of elements that you run the algorithm over increases.

If you have an algorithm with a complexity of (n^2 + n)/2 and you double the number of elements, then the constant 2 does not affect the increase in the execution time, the term n causes a doubling in the execution time and the term n^2 causes a four-fold increase in execution time.
As the n^2 term has the largest contribution, the Big-O complexity is O(n^2).