complexity for nested loops

问题:

I am trying to figure out the complexity of a for loop using Big O notation. I have done this before in my other classes, but this one is more rigorous than the others because it is on the actual algorithm. 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 have arrived that the first loop is of O(n) complexity because it is going through the list n times. As for the second loop I am a little lost! Thank you for the help in the analysis. Each loop is in its own space, they are not together.

回答1:

Consider the first code fragment,

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 for a total of n + n/2 + n/4 + ... + 1 times.

Sum of the first log₂n terms of a G.P. with starting term n and 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 code fragment,

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 call the innermost loop a total of n(n+1)/2 times. The innermost loop is executed at most log<sub>a</sub>n times. Thus the total time complexity of the second code fragment is O(n²log_an).

回答2:

You may formally proceed like the following:

Fragment 1:

Fragment 2 (Pochhammer, G-Function, and Stirling's Approximation):

With log(G(n)).

[UPDATE of Fragment 2]:

With some enhancements from "DISCRETE LOOPS AND WORST CASE PERFORMANCE" publication, by Dr. Johann Blieberger (All cases verified for a = 2):

Where:

Therefore,

回答3:

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

You decrement the outer loop i by diving by 2, and in the inner loop you run i times, so the number of iterations will be a sum over all the powers of two less than or equal to N but greater than 0, which is n^log(n)+1 - 1, so O(n).

The second code block is O(log_a(n)n²) assuming a is a constant.

The two outermost loops equate to a sum of all the numbers less than or equal to n, which is n(n-1)/2, so O(n²). Finally the inner loop is the powers of a less than an upper bound of n, which is O(log_an).