Table 3 Algorithm of the LACP method
From: Mapping biological entities using the longest approximately common prefix method
No | Line | Complexity |
|---|---|---|
1 | Intersection = 0 | O(1) |
2 | FOR i = 1 to min(|S|,|T|) | O(n) |
BEGIN | ||
3 |  HistS.add(S i ) | O(1) |
4 |  HistT.add(T i ) | O(1) |
5 |  FOR (Char c : HistT.Keyset()) | Constant |
 BEGIN | ||
6 |   IF HistS.ContainsKey(c) | O(1) |
7 |   THEN Intersection = | O(1) |
     Intersection + min(HistS.Get(c), HistT.Get(c)) | ||
8 |  END |  |
9 |  IF (i - Intersection) = α | O(1) |
 THEN RETURN | ||
10 | END | Â |
11 | RETURN | O(1) |
Total complexity | O(n) | |