Logarithmic and more for a loop converted to a summary notation

Question

I need help for cycles converted to countries with a sum. Some are easy, but others are a bit complicated. I need to set up the amount designation 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 the following:

Logarithmic (only the correct amount)

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

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

Triple nested (both the amount and step by step why it ends)

 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

Triple nested loop

I will give a simple but very useful method for analyzing such summations in terms of an asymptotic notation.

This is a very general method, you can use it for a large number of summing indices without much effort.

Upper bound

First of all, we give an upper bound for the sum. This is pretty easy:

Bottom line

In this case, the focus is to get the bottom border. A rule of thumb is to reduce the summation range by increasing the subscript of the summation to a fraction of the superscript, and then substitute the new subscript as the superscript in the nested loop. It is also quite easy:

Coming together

From both inequalities you can do the following:

Which in terms of 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 

Answer 2

For a logarithmic cycle:

First, you cannot initialize an index to zero when working with logarithmic loops.

Secondly, the algorithm cycle using the Sigma notation is presented as follows:

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

For three nested loops:

The work of Mark Allen Weiss can help you greatly. See Link.

Answer 3

Logarithmic

The second for-loop never stops ( 0 * 2 = 0 ). I think you asked about this loop:

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

In this case, the complexity expressed through the designation of the sum will be:

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

Triple nested

In this case, it will be a summation:

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

or alternatively if I transpose the triangle:

  number of steps sum -------------------------------------- 1 2 3 4 . n-1 nn(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 (in the second triangle) are also called the numbers of the triangles . So the question is equivalent

"What is the sum of the numbers of the triangle less than or equal to 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 .

Thus, the resulting complexity in large-o O (n ^ 3)