careercup / CtCI-6th-Edition

Cracking the Coding Interview 6th Ed. Solutions
11.33k stars 4.41k forks source link

[10.9] Sorted Matrix Search 'naive' solution has O(N + M) complexity #252

Open Rashair opened 8 months ago

Rashair commented 8 months ago

In the solution to 10.9 task, the 'naive' solution is described as O(M log(N)), which isn't correct for the later algorithm. See example here: https://www.geeksforgeeks.org/search-element-sorted-matrix/