CODEWITHSUNDEEP
algorithmtime-complexity
Vish_TS
Vish_TS

Reputation: 540

Time complexity Analysis of iterative programs

what would be the time complexity of the following

int i,j,k;

for(i=n/2 ;i<=n ;i++)
{
  for(j=1;j<=n/2;j*3)
    {
      for(k=1;k<=n;k=k*2)
        {
           pf('vish');
         }
    }
}

Upvotes: 1

Views: 554

Answers (2)

Ami Tavory
Ami Tavory

Reputation: 76366

You can solve this by applying a number of simple rules.

  1. When you have nested loops, and the boundaries and steps of the inner loops are indpendent of the index of the outer loops, then the number of iterations performed by the innermost body is the multiplication of the number of iterations of each loop.

Here, for example, note that the internal loops (on j and i), for example, don't depend on i.

for(i=n/2 ;i<=n ;i++)
{
  for(j=1;j<=n/2;j*3)
    {
      for(k=1;k<=n;k=k*2)

  1. If the boundaries are Θ(n), and the increments are fixed additions, the number of iterations is Θ(n). So, for example

    for(i=n/2 ;i<=n ;i++)

is performed Θ(n) times.

  1. If the boundaries are Θ(n), and the increments are fixed multiplications, the number of iterations is Θ(log(n)). So, for example

    for(j=1;j<=n/2;j*3)

is Θ(log(n)).

  1. A constant function is O(1).

    pf('vish');

is O(1).

Combining the above rules, we have an O(1) function being performed Θ(n) Θ(log(n)) Θ(log(n)) times. The complexity is Θ(n log(n)2).

Upvotes: 0

Jean Logeart
Jean Logeart

Reputation: 53839

Let's look at how many times each loop is executed:

for(i=n/2 ;i<=n ;i++)       // executed O(n) times
{
  for(j=1;j<=n/2;j*3)       // executed O(log_3(n)) times
    {
       for(k=1;k<=n;k=k*2)  // executed O(log_2(n)) times
        { 
          pf('vish');
        }
    }
}

Assuming pf is O(1) (constant time), the overall complexity is O(n * log(n)^2).

Upvotes: 1

Related Questions