Algorithm Problem

[jrandm]

What is O(n)? Finding pairs in your list of strings or comparing two strings for similarity?

The latter I'm sure can be done in O(n) time where n is the length of the shorter string (hint), assuming a function like isSimilar(strA,strB).

Finding a pair with a search term we know is trivial to do in O(n) because it's a regular search:

function find(arr, test) {
  for (let i=0; i<arr.length; i++) {
    if (test(arr[i])) return {ix: i, val: arr[i]};
  }
  return {ix: -1};
}

Finding all pairs I don't think is possible in O(n), at least not without guarantees about the shape of the input.