Complexity Analysis Station [5]

What is asymptotic complexity in the following void function?

What is asymptotic complexity in the following void function?

Ryan is implementing a merge sort algorithm that he heard about in computers class. However, he wasn't paying attention, and ended up implementing the merge sort in a very unusual way.

The standard merge sort takes a list, and recursively splits it in half, until there is only one element left. It then uses the idea that two sorted lists can be easily merged in O(n)time using "two pointer technique" (this step is usually called merge).

Ryan doesn't know about two pointer technique, however, so he decided to replace merge with a bubble sort! The bubble sort runs in O(n^2) time.

What is the runtime of this merge sort implementation?

Write a function named "rotate_right" that takes as its argument an array of floating point values and an integer that tells the number of cells in the array.

The function should shift the contents of each cell one place to right, except for the last cell which should be moved into the cell with subscript 0. Thus for example if the function looks like the first table above should end like the second one

Suppose a sequence A of n numbers should already be in ascending order. Thus for the

sequence (6,2,9,5,8,7) there are 6 pairs that are out of sequence:

(6,2) , (6,5) , (9,5) , (9,8) , (9,7) , (8,7)

• Implement an algorithm to return the number of these out-of-order pairs.

Hint: An out-of-order pair (Ai,Aj) is such that: ( i < j ) AND (Ai > Aj).

• Determine T(n) = number of array element comparisons.

• What is the Big-O of this algorithm?