retagged by
285 views
5 votes
5 votes

Consider the following pseudo-code of function fun(). fun() takes k arrays as input and return merged array of all. Assume that merge function takes $O(p+q)$ where $p$ is length of first input array to merge and $q$ is length of second input array to merge.
In the pseudo code, size of B and C are $kn/2.$
Let $T(k)$ is time complexity for fun() if there are $k$ input arrays of size $n$

fun (X1[1...n], X2[1...n],....,Xk[1...n]){
    
    if k>1 then
        m = k/2
        𝐵[1...mn] = fun(𝑋1,𝑋2,…,𝑋𝑚)
        𝐶[1⋯(𝑘−𝑚)𝑛] = fun(𝑋𝑚+1,𝑋𝑚+2,…,𝑋𝑘)
        RETURN merge(𝐵,𝐶)
}



What will be value of $T(k) ?$

  1. $T(k)=O(n k \log (n k))$
  2. $T(k)=O(n k \log k)$
  3. $T(k)=O(n k \log n)$
  4. $T(k)=O(n \log nk )$
retagged by

1 Answer

8 votes
8 votes

Answer B

Let $T(k)$ be the running time to merge $k$ arrays, where each of them has $n$ elements. We have the following recursion:
$$T(k)=2 T(k / 2)+O(k n)$$
Again, we can use the recursion tree method to solve this recursion. Also, you can observe that $n$ is independent of $k$, therefore, this is exactly similar to the recursion we saw for the running time of Merge sort, with an extra $n$ at each level. So, we have:
$$T(k)=O(n k \log k).$$

 

 

This question is inspired from one of the popular GATE PYQ: https://gateoverflow.in/1762/Gate-cse-2012-question-39

For this GATE PYQ if we put $k=n$ in the above time complexity AFTER solving reccurance then we get $$T(k)=2 T(k / 2)+O(k\times n) =O(nk \log k) =  O(n^2 \log n) $$

The amazing and important point is: We can not put $k=n$ before solving recurrence, putting $k=n$ before solving recurrence will get you the wrong answer. (You should know why it is the case if you can not understand then spend a few hours in understanding and then tag   under PYQ comment section.)

Putting $k=n$ before solving recuurance: 

$$T(k)=2 T(k / 2)+O(k\times n) \\\implies T(n)=2 T(n/ 2)+O(n^2) = O(n^2)  \color{red}{\text{ WRONG}} $$

edited by
Answer:

Related questions