You seem to think that the complexity of an algorithm is linked to the number of nested loops. It is not the case. The following piece of code is O(1):

for i in [1.. 10^15]:
    for j in [1.. 10^15]:
        for k in [1.. 10^15]:
            dosomethingO1()

Complexity is related to the rate of growth of the number of operations. Unrolling your loop does not change that. So:

foreach(element in myArray) {
    doSomeAction(element);
}

Has 0(1) if the number of elements in myArray is bounded. The complexity will be decided by the number of iterations in the while loop.

About your grid example: if n is the number of cells and your grid is represented as a nested array, looping over those arrays still yields O(n) complexity.

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:

(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:

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