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

Q1 is also two way merge right?
1.0(nloglogn) 2.i have confusion in this
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 :)
why more than 1 question is posted at once?
This is related to one topic and similar type

@Soumya Tiwari

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

is the correct answer

can you explain $(2)?$

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 Answer

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

Related questions

0 votes
1 answer
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.
asked Oct 27, 2018 in Algorithms argha1992 172 views
0 votes
0 answers
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
asked Nov 22, 2017 in Algorithms Akash Mishra 335 views
3 votes
0 answers
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.
asked Aug 6, 2016 in Algorithms sh!va 741 views
0 votes
3 answers
If we talk about that since since we cant access any random element in a linked list for that reason quick sort cant be used for linked lists ,then in merge sort also we need a middle element for splitting so then how do we actually use merge sort then , also ... only add up with the time taken for partition as such no issue in it then why can't we use quicksort for implementing linked lists?
asked Jul 17, 2015 in Algorithms radha gogia 638 views