Time complexity of building of merge sort tree

Правка en1, от Jim_Moriarty_, 2020-03-27 08:08:48

Can anyone explain !! How the complexity of building the merge sort is O(nlog(n)) . As if we build segment tree for maximum query it will take O(n) time because we had to cover approx 2*n to 4*n nodes and at each node merging two children nodes took O(1) time. But here in merge sort merging two children nodes takes O(n) time . So how come the complexity is O(nlog(n))?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Jim_Moriarty_ 2020-03-27 08:08:48 418 Initial revision (published)