How can I tell how many times these nested statements will execute?

Question

I have the following pseudocode:

SelectionSort(A)
    n = A.length
    for j=1 to n-1
        smallest = j
        for i=(j+1) to n
            if A[i] < A[smallest]
                smallest = i
        exchange A[j] with A[smallest]

I think that the first for-loop test will execute n times, and the nested for-loop will execute 1 + 2 + ... + n = n(n+1)/2 times (please correct me if i'm wrong). But I don't understand how I can tell how many times the nested if-statement will execute? Is it 1/2 * n(n+1)/2 ?

Answer 1

The outer for-loop would run for n times. But, it also holds an inner for-loop which is dependent on the vale of j.

I think that the first for-loop test will execute n times, and the nested for-loop will execute 1 + 2 + ... + n = n(n+1)/2 times.

The inner for-loop will run (n-1)+(n-2)+...+1 times based on all the iterations of outer for-loop. So, the net iteration of the loop-statements combinedly would be (n-1) + (n-2) + (n-3) + ... + 1 = (n-1)*n/2 = (n²-n)/2 times.

But I don't understand how I can tell how many times the nested if-statement will execute? Is it 1/2 * n(n+1)/2 ?

As the inner-if statement is dependent on the array elements, it is not possible to directly ascertain exactly how many times it will run.

But, it is for sure that in the worst-case condition,as it is located in the inner for-loop, the maximum number of possible execution(in the worst case) of the if-statement will be (n²-n)/2 times.

So, the worst-case complexity of execution of if-statement is O(n²)

Answer 2

The outer loop shall run from 1 to n-1, hence n-1 times.
The inner loop shall run from j+1 to n times. This means that when j is 1, it will run from 2 to n times (n-1 times) and when j is n-1, it will run from n to n times (1 time).

Hence the inner loop shall run (n-1 + n-2 + ... + 1) times = n(n-1)/2 times.

The if statement shall execute the same number of times as the inner loop does. Ofcourse the conditional statments shall depend on the result of if conditional.