The Gateway to Computer Science Excellence
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 by Veteran (58.9k points) | 137 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.
by (11 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,309 answers
105,024 users