Hello I have an algorithm homework could you help me? DEFINITION: For an integer array S1,a₂,a₃,....,a_n> of size n, we say that the pair (i , j ) of indices is an inversion with respect to S if and only if a_i>a_j and i. [1 Points] For some integer array S of size n, give tight lower and upper bounds for the number of inversions with respect to S. You need to prove that your bounds are actually tight. [1 Points] Give a tight bound for the running time of the Insertion Sort algorithm in terms of n (the size of the input array) and the number of inversions in the input array. [1 Points] Assume that you took some integer array S of size n with distinct elements, and randomly shuffled its elements such that the probability of any element occurring at any index is after the random shuffling. Let be a random variable denoting the number of inversions after the shuffling. What is [1 Points] Deduce the best case, average case and worst case running time of the Insertion Sort algorithm in terms of the input size from what you have obtained above.

Transcribed image text