# Self doubt on sorting

363 views
$(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?
2
3. t(n)=o(n)[median]+o(n)[partioning]+0(1)[swapping with last element]+2t(n/2)  ->   o(nlogn)
4.t(n)=0(n)+0(1)+0(n)+t(n/4)+t(3n/4)->0(nlogn)

Q1 is also two way merge right?
0
1.0(nloglogn) 2.i have confusion in this
0
1.O(nloglogn) Create min heap with first element for logn array and extract minimum (logn*n/logn times) why? There are total of logn*n/logn elements.Each extraction take O(loglogn) so total complexity O(logn+logn*n/logn*loglogn)

2.I think for this sorting each string take nlogn time so sorting n strings take (n^2logn)

3.In this case as we are taking median element so in worst case also the array will be partitioned into n-1/2 and n-1/2 size so complexity will be O(nlogn)

4.For this using the same approch as in 3rd We can get O(nlogn) time but I'm still not sure.

Please correct if I'm wrong :)
0
why more than 1 question is posted at once?
0
This is related to one topic and similar type
0

$(1)O(nloglogn)$                       $(2)O(n^{2}logn)$               $(3)O(nlogn)$            $(4)O(nlogn)$

can you explain $(2)?$

1
What I thought is perform merge sort for n letters in string will take O(nlogn) time so for n strings it's O(n^2logn)

By 2-way merge Question is specifying that sorting is done using merge sort by dividing recursively the array into size of 2 and performing bottom up merging.

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.
0
but in first case 2 way merge sort not written how can you apply  2 way merge? or it is bydefault?

## Related questions

1
172 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 log n).Please answer in terms of the asymptotic notation.
2
335 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)/2 B.) n(n-1)/4 C.) n(n+1)/2 D.) n!/2
3
741 views
A and B are sorting a set of decimal numbers. A's approach: The elements put in 'buckets' of incremental ranges (e.g. 0-9, 10-19, ... 90-99) Each 'bucket' is sorted and merges sorted buckets into one array. B's approach The elements put ... efficiently. IV) A is performing Radix sort and can sort sparse arrays efficiently and B is performing Bucket sort and can sort dense arrays efficiently.