GATE CSE 1989 | Question: 2-iii

Question

Match the pairs in the following:$$\begin{array}{ll|ll}\hline \text{(A)} & \text{$O (\log n)$} & \text{(p)} & \text{Heapsort} \\\hline  \text{(B)} & \text{$O (n)$} & \text{(q)}& \text{Depth-first search} \\\hline   \text{(C)}& \text{$O (n \log n)$} & \text{(r)}  & \text{Binary search} \\\hline  \text{(D)} & \text{$O (n^2)$} &\text{(s)}  & \text{Selection of the $k^{th}$ smallest element in a set of $n$ elements}  \\\hline \end{array}$$

Comments

for kth smallest using Partition() check this question https://gateoverflow.in/8243/gate2015-2-45

---

we can also find kth smalest element using min heap concept .

build min heap for n element => $O(n)$

find the kth smallest element:

Delete smallest element =>$O(1)$ (delete) +$O(logn)$ (Heapfiy) => $O(log n)$

For K elements its $O(klog n)$ => $O(log n)$ as k is constant

Overall: $O(n) + O(log n)$ => $O(n)$

and for k deletion it will take $O(klogn)$ where $k$ is a constant so $log$ $n$ so overall it will take $O(n)+O(logn)= O(n)$

---

smsubham

known as selection procedure.

Answer 1

$$\begin{array}{|ll|ll|}\hline \text{(A)} & \text{$O (\log n)$} & \text{(r)} & \text{Binary search} \\\hline  \text{(B)} & \text{$O (n)$} & \text{(s)}& \text{Selection of the $k^{th}$ smallest element in a}\\& && \text{set of $n$ elements (Worst case)} \\\hline   \text{(C)}& \text{$O (n \log n)$} & \text{(p)}  & \text{Heap sort} \\\hline  \text{(D)} & \text{$O (n^2)$} &\text{(q)}  & \text{Depth-first search }\\&&&\text{(It will be $O(n+m)$ if the graph is given in}\\&&&\text{the form of adjacency list. But if the graph} \\&&&\text{is given the form of adjacency matrix then the}\\&&&\text{complexity is $O(n \times n)$, as we have to traverse}\\&&&\text{through the whole row until we find an edge)}  \\\hline \end{array}$$PS: $k^{th}$ smallest element can be found in $O(n)$ time using partition algorithm.

$T(n)=T(n/2)+n$ (For finding $k^{th}$ smallest element) if the graph is given in the form of adjacency list and by Masters Theorem it will be done in $O(n)$.

Comments

but that will be inconsistent. 

the selected answer matches worst case time complexities of best known algorithms for all problems.

In your case, you are assuming $m = n$, which is true for sparse graphs, but for dense graphs $m = O(n^2)$, so clearly it's not worst case.

For $k^{th}$ smallest element, there is an efficient algorithm with $O(n)$ worst case.  (Page 220 CLRS) or this

So, in your case you are talking about a naive algorithm, but there can be many of those, even $O(n \log n)$ too, by sorting. 

 

 

 

---

@toxicdesire

Sorry for the disturbance $;)$ I was not aware about this algorithm.

For kth smallest element, there is an efficient algorithm with O(n) worst case.  (Page 220 CLRS) or this

Thanks for the explanation.

---

Read all these articles for the Selection of the kth smallest element in a set of n elements.

From simple method to most optimized method.

1.Simple methods: worst-case O(n^2)

https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

2.Using partition with random pivot element: expected time O(n) but worst time complexity O(n^2).

https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-2-expected-linear-time/

3.Using partition with the median as pivot: worst time complexity O(n).

https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/

Answer 2

(A) O(logn)	(p) Binary search since applied on sorted so take logn time only evry time half number visit.
(B) O(n)	(q)  Selection of the kth smallest element in a set of a elements [ using partition algorithm ]
(C) O(nlogn)	(r)   Heapsort [O(n) + (nlogn)
(D) O(n2)	(s) Depth-first search [using Adjacency Matrix in worst case visit each entry ]

Comments

@Aks9639

So, heap-sort and build-heap is not same thing??

Where is difference in both??

---

@srestha mam !

heap sort and build heap is completely a different thing not only acc to their procedure working point of view,  but  also their analysis part too.

analysis part of heap sort is not a big deal we can easily prove it O(n logn) like page 148 of CLRS. We make (n−1) calls to Heapify, each of which takes O(log n) time. So the total running time is O((n − 1) log n) = O(nlogn).

but build_heap_analysis is quite complicated, i have a very rough idea about it , as far as i know acc to CLRS book this perform aggregate analysis which is a part of amortized analysis(not in gate syllabus) .

This is the second time we have seen a relatively complex structured algorithm, with doubly nested loops, come out with a running time of Θ(n). (The other example was the median algorithm, based on the sieve technique).

---

@srestha and moreover,

 there are situations where you might not need to sort all of the elements. For example, it is common to extract some unknown number of the smallest elements until some criterion (depending on the particular application) is met. For this reason it is nice to be able to build the heap quickly since you may not need to extract all the elements. isn't it !

Answer 3

 

(A) O(logn)     Binary search

 

(C) O(nlogn)    heap sort 

I think this two are straight forward.

 

(B) O(n) for BFS and DFS it takes O(E+V) time, here we may assume that n is number of vertices or number of edges depending on which one is greater 

D) O(n2)  please refer case 4 on  https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/ and 

here we are using modified version of quick sort,

for example if we want to find 3 largest element i.e. k=3 , then at some point while execution of quick sort , it will pick some element as pivot for current loop and will put it at third position. 

Worst case complexity is O(n^2) . average case is O(n) bu we always go for worst case hence   O(n^2)                    .                  

Comments

But  Depth-first search also has  O(n²) [using Adjacency Matrix in worst case visit each entry ]

---

I think we must find worst case time complexity for best algorithm.

So we should code DFS using Adjacency list