CODEWITHSUNDEEP
c++algorithm
Anatoly
Anatoly

Reputation: 1916

How many times increment will be executed?

I have the following code

    int cnt = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = i + 1; j < N; ++j)
        {
           if(a[i] + a[j] == 0)
           { ++cnt;}
        }
    }

Where N is a number of elements in the array.

I started to learn algorithms and I trying to find how many times increment will be executed?

For i it will be N times.

For j it will be N-1 times when i = 0, N-2 when i = 1 etc. So N-1 + N-2 + ... + 0 = ((0 + N-1)/2)*N = N*(N-1)/2

So how many times cnt++ will be executed?

To answer for this question we need to find how many times == will be executed? Of course it will be in range. From 0 to some value. And our final answer will be in the range from 0 + number of(++i) + number of(++j) to some value + number of(++i) + number of(++j).

Let's find this some value

It will be 1...N-1 when i=0, 2...N-2 when i=1 etc so N-1 + N-2 + ... + 0 = N*(N-1)/2

So the answer will be from N*(N-1)/2 to N + N(N-1)/2 + N(N-1)/2, so from N*(N-1)/2 to N^2

But R.Sedgwick said at the 33 slide that http://www.cs.princeton.edu/courses/archive/spring15/cos226/lectures/14AnalysisOfAlgorithms.pdf

the answer will be from N*(N+1)/2 to N^2

Why? Am I wrong? Where?

Upvotes: 3

Views: 369

Answers (1)

user1196549
user1196549

Reputation:

The inner loop (== test) is indeed executed N(N-1)/2 times.

For this reason, the increment (++cnt) is potentially executed between 0 and N(N-1)/2 times.

These two bounds can be reached: 0 when all a[k] > 0, and N(N-1)/2 when all a[k] == 0.

For the total count of increments, add N for the outer for loop and N(N-1)/2 for the inner for loop, and get between N(N+1)/2 and N² inclusive.

Upvotes: 4

Related Questions