Swapping ints 2

We know that the insertion sort algorithm has a worth-case running time of O(n2)O(n^{2}) in general case. What if we could bound the algorithm for specific instance of the problem. One way to do that is by checking the number of swap operations needed by insertion algorithm to sort a list.

In the permutation of a1ana_{1}\cdots a_{n} of nn distinct elements the list inversion are pair of elements (ai,aj)(a_{i},a_{j}) such that i<ji<j and ai>aja_{i} > a_{j}. What is the worst-case running time if the inputs are restricted to permutations of 1n1\cdots n with at most nn inversions?

×

Problem Loading...

Note Loading...

Set Loading...