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.

Is your comment in the last paragraph describing your thoughts on the first problem or the second one? — hatchet - done with SOverflow
– hatchet - done with SOverflow, Commented May 24, 2013 at 20:58
There is no list in your code, so I assume by "going through the list" you simply mean that x += a is executed n times, right? If so, how did you come to that conclusion? — sepp2k
– sepp2k, Commented May 24, 2013 at 21:31

Deepu · Accepted Answer · 2013-05-25 19:20:41Z

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

Mohamed Ennahdi El Idrissi · Accepted Answer · 2014-06-09 00:22:17Z

1

You may formally proceed like the following:

Fragment 1:

enter image description here

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

enter image description here

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

enter image description here

Where:

enter image description here

Therefore,

enter image description here

edited Jun 9, 2014 at 0:22

answered Apr 9, 2014 at 20:03

Mohamed Ennahdi El Idrissi

2,9872 gold badges21 silver badges35 bronze badges

Comments

qwwqwwq · Accepted Answer · 2013-05-24 21:39:56Z

0

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

edited May 24, 2013 at 21:39

answered May 24, 2013 at 21:18

qwwqwwq

7,3592 gold badges32 silver badges51 bronze badges

2 Comments

Hassan Bendouj Over a year ago

can you please more expling why O(2log(n))

sepp2k Over a year ago

2^log_2(n) is just n, but I don't think you're right here. I'm pretty sure it actually is O(n).

Collectives™ on Stack Overflow

complexity for nested loops

3 Answers 3

Comments

Comments

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

2 Comments

Linked

Related