edited by
4,939 views
12 votes
12 votes

A cache aware sorting algorithm sorts an array of size 2k with each key of size 4 Bytes. The size of the cache memory is 128 Bytes and algorithm is the combination of merge sort and insertion sort to exploit the locality of reference for the cache memory (i.e. will use insertion sort while problem size equals cache memory).

Best case and worst case running time of the algorithm respectively is:

A) 2k-5 [1+log22k-5], 2k-5 [25+log22k-5]

B) 2k-5 [1+log22k-5], 25 [2k-5+log22k]

C) 2k [1+log22k-5], 2k [25+log22k-5​​​​​​​]

D) 2k [25+log22k-5], 2k [25+log22k​​​​​​​-5]

edited by

1 Answer

Best answer
15 votes
15 votes
  • If we sort $\frac{n}{x}$  lists each of $x$ elements using indertion sort and then merge them using normal merge sort then totol overall complexity would be $\Theta\left \{ \frac{n}{x}.IN(x) + n.\log \left ( \frac{n}{x} \right ) \right \}$. Where $IN(x)$ is the time taken by the insertion sort to sort $x$ element list.
  • Here $x = 2^5 = \text{cache size}$.
  • So, putting insertion sort worst case $IN(x) = x^2$ we got the worst case of the new algorithm.
  • putting insertion sort best case $IN(x) = x$ we got the best case for this new algorithm

$$\begin{align*} &\text{Best complexity when insertion sort gives best}\\ &\Rightarrow IN(x) = x = 2^5 \\ &\Rightarrow \text{Best Conplexity} = \frac{n}{x}.IN(x)+ n.\log \left ( \frac{n}{x} \right ) \\ &\Rightarrow \text{Best Conplexity} = \frac{2^k}{2^5}.2^5 + 2^k.\log \left ( \frac{2^k}{2^5} \right ) \\ &\Rightarrow \text{Best Conplexity} = 2^k. \left ( 1 + \log \left ( 2^{k-5} \right ) \right ) \\ \\ &\text{Now , } \\ &\text{Worst complexity when insertion sort gives Worst}\\ &\Rightarrow IN(x) = x^2 = \left ( 2^5 \right )^2 \\ &\Rightarrow \text{Worst Conplexity} = \frac{n}{x}.IN(x)+ n.\log \left ( \frac{n}{x} \right ) \\ &\Rightarrow \text{Worst Conplexity} = \frac{2^k}{2^5}.\left ( 2^5 \right )^2 + 2^k.\log \left ( \frac{2^k}{2^5} \right ) \\ &\Rightarrow \text{Worst Conplexity} = 2^k. \left ( 2^5 + \log \left ( 2^{k-5} \right ) \right ) \\ \end{align*}$$


NOTE:

  • Merge sort in call cases will take (total_no_of_elemets)* $\log$ (no_of_small_problem)
edited by

Related questions

8 votes
8 votes
2 answers
2
0 votes
0 votes
2 answers
3
_Madhuri asked Oct 9, 2021
634 views
The complexity of comparison based sorting algorithm is (nlogn) .How?
0 votes
0 votes
0 answers
4