Timeline for Hint on median of two sorted lists, logarithmic time
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 14, 2019 at 23:27 | comment | added | Steven Stadnicki | @nilanjanaLodh are you wondering about the median algorithm itself or the 'merged position search'? | |
| Nov 14, 2019 at 23:09 | comment | added | nilanjanaLodh | @StevenStadnicki I can't figure out how the complexity is not O(log m * log n) .. could you please point me in the right direction.. how is it O(logm + log n) | |
| Dec 12, 2017 at 23:27 | comment | added | Steven Stadnicki | You have to be a little delicate in the analysis, though; at first glance this doesn't actually do better than $O(\log^2 n)$ running time (assuming that both lists are of size $n$), but the point is that the subsequent position-finding doesn't take 'full' time... | |
| Dec 12, 2017 at 22:09 | history | answered | Yuval Filmus | CC BY-SA 3.0 |