794 views
0 votes
0 votes
$(1)$Give $"logn"$ Sorted lists each of size $"\frac{n}{logn}",$what is the total time required to merge them into one single list?

$(2)"n"$ strings each of length $"n"$ are given them, what is the time taken to sort them,$2-$way merge?

$(3)$The median of "n" elements can be found in $O(n)$ time.Which one of the following is correct about the complexity of quicksort,in which the median is selected as pivot?

$(4)$In quicksort,for sorting $'n'$ elements,the $\frac{n}{4}th$ smallest element is selected as pivot using $O(n)$ time algorithm.What is the worst case time complexity of quicksort?

1 Answer

0 votes
0 votes
1. for logn sorted lists, each of size n/logn, if we apply 2-way merging than the time-complexity will be - O(n.loglogn).

we have logn lists each of size n/logn. And now if I merge them by 2-way merging ,then at each level there are : - logn*n/logn=n elements.

And total no. of levels are= log(no. of sorted list)=log.logn .Thus Total time complexity=n.loglogn.

Related questions

0 votes
0 votes
2 answers
1
argha1992 asked Oct 27, 2018
558 views
What is the average case time complexity of the best sorting algorithm for an array having 2^n^2 elements .I know that the best sorting algorithm is no better than O(n lo...
0 votes
0 votes
0 answers
2
Akash Mishra asked Nov 22, 2017
724 views
The average number of inversions in an unsorted array of n elements is?(Two elements a[i] and a[j] form an inversion if a[i] a[j] and i < j)A.) n(n-1)/2B.) n(n-1)/4C.) n...
6 votes
6 votes
2 answers
4