SET PYQs from Unit-7

 A complete binary tree has depth, given by the formula (where n is the number nodes)

In a complete binary tree with n nodes the height of the tree is log(n+1) (depth  = height)

Consider an array with 50 elements. How many move operations will be performed for deleting first 25 elements from 25th location and remaining 25 elements from the 0th location, one by one?

When you delete elements from an array, it typically involves shifting the remaining elements to fill the gap.

Let us take the array index from 0 to 49 for 50 elements.

When you delete 25th location element, you have to move 24 elements (location 26 to 49) back to one position (25 to 48). This happens after the first element is deleted.

The elements are deleted one by one. 
For 1st element, there are 24 moves, for 2nd element, there are 23 moves, it goes on...
Total number of moves for deleting 25 elements = n (n - 1) / 2 where n is the number of elements.

Total number of moves for deleting 25 elements from 25th location = n (n - 1) / 2
                                                                                                             = 25 x 24 / 2 = 25 x 12
                                                                                                             = 300

Total number of moves for deleting 25 elements from 0th location   = n (n - 1) / 2
                                                                                                             = 25 x 24 / 2 = 25 x 12
                                                                                                             = 300

Total number of moves = Moves from 25th location + Moves from 0th location
                                      = 300 + 300
                                      = 600

While performing insertion sort on an array of N distinct numbers, the number of interchanges is given by

In insertion sort, each iteration removes an element from the input data and inserts it into the correct position in the list being sorted.

An interchange or swap occurs when elements in the array need to be rearranged to insert the current element into its proper position. Specifically, for each element that is moved past a larger element during the sorting process, an interchange is counted.

In insertion sort on an array of N distinct numbers, the number of interchanges made is equal to the number of inversions present in the array. Inversions are pairs of elements where the element at the smaller index is greater than the element at the larger index.

(1) When the input list is already sorted, the insertion sort performs minimal comparisons.
       Best Case = N−1

(2) For a randomly ordered array, the number of inversions (and interchanges) are given by:
       Average Case = N (N-1) / 4

(3) In the worst-case scenario, the array is sorted in descending order.
      Worst Case = N (N-1) / 2

The question is about distinct numbers, this matches with the randomly ordered array scenario.
So, the number of interchanges = N (N-1) / 4