-1

Following is the code:

for (i = n-1; i>0; i--)
    for (j=0; j<i; j++)
      if (arr[i] < arr[i+1])
      {
          temp = arr[i];
          arr[i] = arr[i+1];
          arr[i+1] = temp;
      }

I could find for the outer for outer for loop will execute n times and the inner for loop will be executed i+i-1+i-2+....+1 i(i+1)/2=(i^2+i)/2 and the if condition will be checked for (i-1)*i/2=(i^2-i)/2 times but I am confused for the statements in if condition and also correct me if I am wrong for the my above calculations too.

Anon2002
  • 3
  • 3
  • 1
    What is "frequency count method"? – PaulMcKenzie Oct 16 '21 at 14:35
  • 1
    I'm also not sure what you mean by "frequency count method". But the inner loop executes, on average, half as much as the outer loop. If you graphed all the i,j pairs that the inner loop encounters, they would fill a triangle on the plane, a shape whose area is proportional to a square. So it's O(N^2). – Wyck Oct 16 '21 at 14:38
  • 2
    Also this code is obviously buggy. It repeatedly compares `arr[i]` and `arr[i+1]` for the same value of `i`. – Stef Oct 16 '21 at 14:39
  • Frequency count method is the basic calculation of how many times a statement in a code is executed unlike Big O notation which gives only the count for maximum time.It includes all the statements with constant time complexity too. – Anon2002 Oct 16 '21 at 14:41
  • 1
    @Anon2002 we have profilers for that sort of analysis as the generated code with optimisation does not have to match (on a frequency count basis) the original source code. Without optimisation we are in who cares territory. – Richard Critten Oct 16 '21 at 15:03
  • The `if` condition is tested exactly `(n-1)*n/2` times. (Not `(i-1)*i/2` times.) But otherwise your calculation is correct. – Wyck Oct 16 '21 at 15:11
  • @Anon2002 *how many times a statement in a code is executed* -- C++ compilers when the code is optimized do not work this way. If you want an example of how irrelevant it is to attempt to count how many times a statement is executed, [look at this question and answer](https://stackoverflow.com/questions/48584084/how-to-move-the-first-digit-to-the-end-of-a-number-in-c/48587366#48587366). The count for the number of times those lines are exected is .... **0**. The reason is that the compiler figured out what the intent of the code was, and generated the answer *at compile time*. – PaulMcKenzie Oct 16 '21 at 20:17

1 Answers1

2

for n = 5, the values of i and j encountered when the if statement is executed can be listed as follows:

(4,0) (4,1) (4,2) (4,3)
(3,0) (3,1) (3,2)
(2,0) (2,1)
(1,0)

I arranged the items like that on purpose because they form a triangle.

####
###
##
#

To count how many items are in this triangle we can mirror the triangle and count each item twice. There are two ways to do it neatly depending on whether you place the mirrored items to the right or below.

####o
###oo
##ooo
#oooo

####
###o
##oo
#ooo
oooo

Either way, by inspecting width times height, this can easily be seen to be a rectangle of either n * (n-1) or (n-1) * n items (equal area in both cases). And since we counted each element twice, we can divide by two, and use (n-1) * n / 2 as the formula for the number of items.

Therefore your if condition will be computed exactly (n-1) * n / 2 times.

You also correctly expanded this expression to be ((n*n) - (n)) / 2 which is also equal to (n^2 - n) / 2.

But a few things were bad...

You said (i-1)*i/2, using i instead of n. That's not right.

Your code appears to intend to compute a Bubble sort. And the index for the if condition and its block should be j (not i) throughout. (You were comparing arr[i] to arr[i+1] for the same value of i repeatedly in the inner loop. The actual swap would be evaluated at most once for a given value of i, in that case, or not at all, depending on the values of arr.)

The code you intended was likely:

for (i = n-1; i>0; i--)
    for (j=0; j<i; j++)
      if (arr[j] < arr[j+1])
      {
          temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;
      }
Wyck
  • 10,311
  • 6
  • 39
  • 60
  • Means from this I can say that the outer for loop will be executed n times and the inner for loop will be executed n(n+1)/2=(n^2+n)/2 and the if condition will be checked (n-1)n/2=(n^2-n)/2 and the statements inside if condition will be executed atmost once but the condition can be true for multiple of j index in array but we cannot determine how many times it will be true so we cannot determine the exact count for if condition statements right? But for the outer statements of 2 for loops and if condition can I say that the time complexity would be n+(n^2+n)/2+(n^2-n)/2 is this correct? – Anon2002 Oct 17 '21 at 06:50
  • No, you're making it too complicated. The answer is just (n^2-n)/2. – Wyck Oct 18 '21 at 02:32
  • No I need for inner and outer for loop too and that (n^2-n)/2 will only be for the if Statement what about the for loops I need total time complexity – Anon2002 Nov 03 '21 at 05:43
  • I'm sorry, but I don't understand what you're asking for. You'll have to provide a better explanation of how to compute _total time complexity_. I've shown you how to count how many times the loop body executes. Unless you're asking how many times the condition expression is evaluated...is that what you need to know? For the outer loop, it's body is executed `n-1` times and the `i>0` expression is evaluated exactly `n` times, including the last time, where `i>0` returns false and the loop exits. Similarly to above, `j – Wyck Nov 03 '21 at 12:46