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

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