Logarithmic and other for loop converted to sum notation

Question

I need help with for loops converted to a sum nations. Some of are easy but others are a bit tricky. I need getting the sum notation setup correctly.

Like this: (Correct for example loop)

As an example:

for (int i = 0; i < n; i = i + 1)  
  a = i; //cost 1

Sum 1, i=0 to n-1 == n.

I need help with following:

Logarithmic (just the correct sum notation)

for (int i = 0; i < n; i = 2 * i)  
  a = i; //cost 1

Sum 1, i=0 to log(n)-1 == log n. Correct??

Triple nested (both sum notation and step by step why it ends up like it)

for (int i = 0; i < n; i = i + 1)  
for (int j = 0; j <= i; j = j + 1)  
for (int k = 0; k <= j; k = k + 1)  
  a=i; //cost 1

Answer 1

Logarithmic

The second for-loop will never stop (0 * 2 = 0). I guess, you were asking about this loop:

for (int i = 1; i < n; i = 2 * i)  
  a = i; //cost 1

In this case the complexity expressed via the sum notation will be:

Sum 1, i=1 to log(n-1) == O(log n)

Triple nested

In this case it will be the summation of:

 number of steps                 sum
 --------------------------------------
 1   1   1   1   1   1   .       n
 2   2   2   2   2   .           2(n-1)
 3   3   3   3   .               3(n-2)
 4   4   4   .                   4(n-3)
 .   .   .                       .
n-1 n-1                          2(n-1)
 n                               n

or alternatively if I transpose the triangle:

 number of steps                 sum
 --------------------------------------
 1   2   3   4   .  n-1   n      n(n+1)/2 
 1   2   3   4   .  n-1          (n-1)(n)/2
 1   2   3   4   .               (n-2)(n-1)/2
 1   2   3   .                   4(n-3)
 1   2   .                       .
 1   .                           3
 .                               1

The numbers on the right side (in the second triangle) are also called triangle numbers. So the question is equivalent to

"What is the sum of triangle numbers lower or equal than f(n). (f(1) + f(2) + f(n), where f(x) = x(x+1)/2)."

The answer to this question is

f(n) = n(n+1)(n+2)/6

The proof is here.

So the resulting complexity in big-o is O(n^3)

Answer 2

For the logarithmic loop:

First, you can't initialize the index with zero when dealing with logarithmic loops.

Second, the following is the way to present the algorithmic loop using Sigma notation:

Look at the last slide of this document of Dr. Jauhar.

For the three nested loops:

Mark Allen Weiss work may help you considerably. See this link.

Answer 3

The triple nested loop

I'll give a simple, but a very useful method to analyze such summations in terms of the asymptotic notation.

This is a very general method, you can use it to bound many multiple index summations without a big effort.

Upper bound

First of all, let's derive an upper bound for the sum. It's quite easy:

Lower bound

The trick in this case is to derive the lower bound. The rule of thumb is to reduce the summation range incrementing the lower summation index to the fraction of the upper index and then substitute the new lower index as the upper index in the nested loop. It's also pretty easy:

Putting it together

From both inequalities, you can deduce that:

Which in terms of the asymptotic analysis gives:

As you can see, your triple nested loop has the same asymptotic time complexity as:

for(int i = 0; i < n; i = i + 1)  
   for(int j = 0; j < n; j = j + 1)  
      for(int k = 0; k < n; k = k + 1)  
         //operations of cost 1