diff options
| author | Mattias Andrée <m@maandree.se> | 2026-02-22 13:41:30 +0100 |
|---|---|---|
| committer | Mattias Andrée <m@maandree.se> | 2026-02-22 13:41:30 +0100 |
| commit | 97984119a2509686f18ca6bebff75a58294069be (patch) | |
| tree | a4126679a8a3d0bfbaf2481baf036609cbd292fe /README | |
| parent | Update e-mail (diff) | |
| download | binary-multisearch.h-master.tar.gz binary-multisearch.h-master.tar.bz2 binary-multisearch.h-master.tar.xz | |
Signed-off-by: Mattias Andrée <m@maandree.se>
Diffstat (limited to 'README')
| -rw-r--r-- | README | 8 |
1 files changed, 4 insertions, 4 deletions
@@ -3,14 +3,14 @@ Binary multisearch Description: Given a sorted list of unique items, find in another sorted list their position or if missing where they - ought to be inserted. Both list must allow random access. + ought to be inserted. Both lists must allow random access. Complexity: n = number of elements in target list - m = number of element to locate + m = number of elements to locate Time complexity: O(S(n) + m) - S = time complexity function of underlaying search algorithm, + S = time complexity function of underlying search algorithm, e.g. S(n) = O(log n) in average case for binary search given O(1) comparison. Auxiliary space complexity: @@ -21,4 +21,4 @@ Notes: In online version, positions for elements are returned in arbitrary (deterministic) order, rather than sequential. -I wrote this algorithm back in Feburary 2013. +I wrote this algorithm back in February 2013. |