wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

sorted_list_intersection (426B)

      1 # Sorted list intersection
      2 
      3 - can be done in [linear_time] in both lists
      4 - but if one of the lists is much smaller than the others, you can do [binary_search] of the values of the small list into the big list
      5 
      6 https://stackoverflow.com/a/40538162 lower bound and upper bound
      7 - Theta (n log (m/n)) for n the smaller value
      8 
      9 See also: [set_intersection], [set_intersection_2], [sorted_array]
     10 
     11 Up: [intersection] of [sorted_list]