CODEWITHSUNDEEP
algorithmcomplexity-theory
yashgos
yashgos

Reputation: 23

What will be the time complexity of the following algorithm?

for(i=0;i< m; i++)
{

   for(j=i+1; j < m; j++)
   {

      for(k=0; k < n;k++)
      {
         for(l=0;l< n;l++)
         {if(condition) do something}
      }
   }

}

Upvotes: 2

Views: 711

Answers (6)

snakile
snakile

Reputation: 54521

I assume the time complexity of "do something" is O(S).

Let's start with the most inner loop: It's time complexity is O(n*S) because it does something n times. The loop which wraps the most inner loop has a time complexity of O(n)O(nS)=O(n^2*S) because it does the inner loop n times.

The loop whcih wraps the second most inner loop has a time complexity of O(m-i)*O(n^2*S) because it does an O(n^2*S) operation m-i times.

Now for the harder part: for each i in the range 0...m-1 we do an (m-i)*O(n^2*S) operation. How long does it take? (1 + 2 + 3 + ... + m)*O(n^2*S). But (1 + 2 + ... + m) is the sum of an arithmetic sequence. Therefore the sum equals to m*(m-1)/2=O(m^2).

Conclusion: We do an O(n^2*S) operation about m^2 times. The time complexity of the whole thing is O(m^2*n^2*S)

Upvotes: 1

Rafid
Rafid

Reputation: 20179

In details:

The two first loops will result in (m-1) + (m-2) + (m-3) + ... + 1 repetitions, which is equal to m*(m-1)/2. As for the second two loops, they basically run from 0 to n-1 so they need n^2 iterations.

As you have no clue whether the condition will be fulfilled or not, then you take the worst case, which is it being always fulfilled.

Then the number of iterations is:

m*(m+1)/2*n^2*NumberOfIterations(Something)

In O notation, the constants and lower degrees are not necessary, so the complexity is:

O(m^2*n^2)*O(Something)

Upvotes: 3

user375348
user375348

Reputation: 789

O(m²*n²) *complexity of "something"

Upvotes: 0

Ani
Ani

Reputation: 113402

for(i=0;i< m; i++)
{  
   for(j=i+1; j < m; j++)
   {

The inner loop will run ((m-1) + (m-2) + ... 1) times 

= 1 + 2 + 3 + ...m-1 
= m * (m - 1) / 2

for(k=0; k < n;k++)
{
   for(l=0;l< n;l++)
   {

In this case, the inner loop clearly runs n * n times

So clearly, the number of iterations is exactly

  (m * (m - 1) / 2) * (n * n)
= O(m^2 * n^2)

Obviously, this assumes that if(condition) do something runs in constant time.

Upvotes: 2

user180247
user180247

Reputation:

Looks like O(m^2 n^2) to me, assuming the "something" is constant-time.

Although the j loop starts from a different point with each step, the combined effect of the i and j loops is still an m^2 factor.

Evaluating the unstated condition itself would normally be (at least) a constant time operation, so certainly the loop cannot be faster than O(m^2 n^2) - unless, of course, the "something" includes a break, goto, exception throw or whatever that exits out of one or more of the loops early.

All bets are off if, for any reason, either n or m isn't constant throughout.

Upvotes: 1

agsamek
agsamek

Reputation: 9054

O(m^2*n^2*(compexity of something)). If condition and something are executed in constant time then O(m^2*n^2).

Upvotes: 0

Related Questions