0 votes 0 votes Given two max heap, one of size n and other m. Calculate the time complexity of merging them to get a max heap. DS heap time-complexity merging + – shub2204 asked Dec 5, 2022 retagged Dec 5, 2022 by makhdoom ghaya shub2204 854 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes If we have $n+m$ elements then we can perform build heap on these $n+m$ elements and for that time complexity = $O(n+m)$. Pranavpurkar answered Dec 5, 2022 Pranavpurkar comment Share Follow See all 20 Comments See all 20 20 Comments reply Show 17 previous comments Pranavpurkar commented Dec 7, 2022 reply Follow Share gatecse Sir, i have referred the link , So sir, is it possible to do it in less than $(O(log(m+n))$ also? 0 votes 0 votes gatecse commented Dec 7, 2022 reply Follow Share In the link it is ‘*’ and not ‘+’. We can easily prove that we cannot do better than $O(\log (m+n))-$ how? Because if we can do, then we are improving the lower bound of some already known problems (like searching for an element in a CBT) by reduction. But to prove the lower bound as the one given in the paper it is not easy. And that’s why they used ‘O’ in the paper and not $\Omega.$ Someone else can either give a better $O$ estimate or prove that such a better algorithm does not exist. 1 votes 1 votes Pranavpurkar commented Dec 7, 2022 reply Follow Share @gatecse, Thank you so much sir 🙏 , for this discussion,got to learn a lot and also helped in revising the things. 1 votes 1 votes Please log in or register to add a comment.