1

I've written a special indexOf function for a list of unsorted unique values.

I can search for one or multiple (unsorted) values, passed as array/list, and the function will return me an array/list of indices (possibly empty).

Based on the following circumstances:

  • I know that the values i'm searching for are in the list
  • I don't care about the order in which the indices are returned
  • Uniqueness

I'm doing the following:

  1. Walk through the list (of size n)
  2. Compare the values with all values in the search-list
  3. If there's a match break, add to results, break out of the loop and remove the found value from the search-list (so it's smaller on the next item)
  4. If there are no more values left to search for, break out of the list-traversal.

I'd like to know how to analyse this algorithm, and specifically what the worst-case runtime is. (I guess if I'm searching for all values contained in the list.)

Source in JavaScript:

function multipleIndexOf(search, arr) {

    var searchArr = search.slice(0);
    var result = [];

    /* loop through array */
    for (var i = 0, l = arr.length; i < l; i++) {

        /* loop through search values */
        for (var i2 = 0, l2 = searchArr.length; i2 < l2; i2++) {

            /* if a search value matches... */
            if (arr[i] == searchArr[i2]) {
                /* add to result */
                result.push(i);

                /* remove from array */
                searchArr.splice(i2, 1);

                /* continue search with next */
                break;
            }
        }

        if (searchArr.length == 0) {
            break;
        }
    }

    return result;
}
  • And no, this is not homework. – Fabian Zeindl Nov 26 '13 at 21:15
5

You're going through each item in one collection for each item in another, that's O(N * M) where n and m are the sizes of each collection. The short circuiting doesn't affect the big O representation, as it is measuring the worst case, in which you never exit early. And even in the average case, the short circuiting cuts the time in half. O(N * M / 2) is equivalent to O(N * M).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.