CODEWITHSUNDEEP
algorithmbig-o
Adam Pymont
Adam Pymont

Reputation: 13

How many times can these loops execute?

Hey I'm trying to figure out the growth rate of the nested loop, I know the first loop is will go around 100 times since it can only run 100 times but the 2nd loop I'm not too sure about. Anyone can help me out?

29  for (int i = 0; i < MAX; ++i)
30  {
31     for (int j = 0; m[i] < m[j] && m[j] != 0; ++j)
32     {
33        product = product + (m[i] * n[j]);
34     }
35  }

The full code is here

01  const int MAX = 100;
02  int lowerCount;
03  int higherCount;
04  int equalCount;
05  int product;
06
07  lowerCount = higherCount = equalCount = 0;
08  product = 0;
09
10  for (int i = 0; i < MAX; i++)
11  {
12     if (m[i]  < n[i])
13     {
14         ++higherCount;
15     }
16     else
17     {
18        if (m[i] == n[i])
19        {
20           ++lowerCount;
21        }
22        else
23        {
24           ++equalCount;
25        }
26     }
27  }
28
29  for (int i = 0; i < MAX; i++)
30  {
31     for (int j = 0; m[i] < m[j] && m[j] != 0; j++)
32     {
33        product = product + (m[i] * n[j]);
34     }
35  }
36
37  cout << "lowerCount " << lowerCount << "\n";
38  cout << "equalCount " << equalCount << "\n";`
39  cout << "higherCount " << higherCount << "\n";
40  cout << "product " << product << "\n"";

Upvotes: 1

Views: 183

Answers (2)

David Oragi
David Oragi

Reputation: 36

I think the answer you are looking for is O(N^2 + 2N / (1/2N) + 3n^3) this is clear if you use Ballmers algorithm to work out complexity.

Upvotes: 2

Ilian Iliev
Ilian Iliev

Reputation: 3236

As far as I know, when calculating algorithm complexity you can give big-O for best, worst and average case.

In the case of two nested loops the best case is O(n) - if the inner loop is executed only once(I am ignoring the fact that both loops may process only one iteration). The worst one is O(n*k) - first loop iterates n-times, the inner one iterates k-times.

As Asier has sad we do not know what is in m[i] so there is not idea what the average complexity will be.

Upvotes: 1

Related Questions