Difficulty for nested loops

Question

I am trying to figure out the complexity of a for loop using Big O notation. I have done this before in other classes, but this one is more strict than others because it is on the algorithm itself. The code is as follows:

for(i=n ; i>1 ; i/=2) //for any size n { for(j = 1; j < i; j++) { x+=a } } 

and

 for(i=1 ; i<=n;i++,x=1) //for any size n { for(j = 1; j <= i; j++) { for(k = 1; k <= j; x+=a,k*=a) { } } } 

I came that the first loop has O (n) complexity because it goes through n times. As for the second cycle, I'm a little lost! Thanks for the help in the analysis. Each cycle is in its own space, they are not together.

Answer 1

Consider the first piece of code,

 for(i=n ; i>1 ; i/=2) //for any size n { for(j = 1; j < i; j++) { x+=a } } 

The instruction x+=a is executed a total of n + n/2 + n/4 + ... + 1 times.

The sum of the first log ₂ n members of GP with the initial term n and the common ratio 1/2 is (n (1- (1/2) ^{log ₂ n} )) / (1/2) . Thus, the complexity of the first code fragment is O (n) .

Now consider the second piece of code,

 for(i=1 ; i<=n; i++,x=1) { for(j = 1; j <= i; j++) { for(k = 1; k <= j; x+=a,k*=a) { } } } 

The two outer loops together name the innermost cycle in the sum n(n+1)/2 times. The innermost loop runs no more than log<sub>a</sub>n times. Thus, the total time complexity of the second code fragment is O (n ² log _a n) .

Answer 2

EDIT: I agree that the first block of code is O (n)

You reduce the outer loop i by diving by 2, and in the inner loop you start i times, so the number of iterations will be the sum of all powers of two less than or equal to N, but greater than 0, that n ^{log (n) +1} - 1, therefore O (n).

The second code block is O (log _a (n) n ² ), assuming that a is a constant.

The two extreme cycles are equal to the sum of all numbers less than or equal to n, which is n (n-1) / 2, therefore O (n ² ). Finally, the inner loop is a power of a smaller upper bound n, which is O (log _a n).

Answer 3

You can formally act as follows:

Fragment 1:

Fragment 2 (Pochammer, G-function and Stirling approximation) :

C log (G (n)) .

[UPDATE Fragment 2] :

With some improvements from the publication “DISCRETE VERSES AND USE OF CASES” from Dr. Johann Bleberger (all cases confirmed for a = 2 ):

Where:

In this way,