Give an example of an input sequence that has running time i

Give an example of an input sequence that has running time in Theta (n log(n)) for merge sort, but in Theta (n) for insertion sort.

Solution

Example for merge sort which has running time (n(logn))

Ans. We know that in merge sort we divide a probleminto smaller problems, apply the sorting technique in the smaller sub parts and aain divide them again into smaller parts until all the elements get sorted. When all the elements get sorted, we combine the two sorted subparts for getting the sorted array.

So, if we consider a problem of size n at level 1, then at level 2 subproblem size will be n/2 and merging time will be 2.cn/2 i.e cn , Similarly at level 3 time will be 4.cn/4 i.e also n. So at lth level, the total merging time will be l.cn. When we analyzed binary search tree, we saw that l = logn +1.

So here l.cn cn(logn+1) . When we use big- notation to describe this running time, we can discard the low-order term (+1+1plus, 1) and the constant coefficient (ccc), giving us a running time of \\Theta(n \\lg n)(nlgn).

Example for insertion sort which has running time (n)

Like selection sort, insertion sort loops over the indices of the array. It just calls insert on the elements at indices 1, 2, 3, \\ldots, n-11,2,3,…,n1.

Let\'s take a situation where we call insert and the value being inserted into a subarray is less than every element in the subarray. For example, if we\'re inserting 0 into the subarray [2, 3, 5, 7, 11], then every element in the subarray has to slide over one position to the right. So, in general, if we\'re inserting into a subarray with kkk elements, all kkk might have to slide over by one position. Rather than counting exactly how many lines of code we need to test an element against a key and slide the element, let\'s agree that it\'s a constant number of lines; let\'s call that constant ccc. Therefore, it could take up to c \\cdot kckc, dot, klines to insert into a subarray of kkk elements.

Suppose that upon every call to insert, the value being inserted is less than every element in the subarray to its left. When we call insert the first time, k=1k=1k, equals, 1. The second time, k=2k=2k, equals, 2. The third time, k=3 . And so on, up through the last time, when k = n-1k=n1k, equals, n, minus, 1. Therefore, the total time spent inserting into sorted subarrays is

c.1+c.2+c.3 + ................. + c.(n -1) = c(1+2+3 + ............ + (n-1)) = cn2/2cn/2.

Using big- notation, we discard the low-order term cn/2 and the constant factors c and 1/2, getting the result that the running time of insertion sort, in this case, is (n2).

But this is the worst case complexity.

In the best case, there will be n-1 calls to insert and if each call takes constant time c then time complexity becomes (n).