How to calculate the worst-case runtime of this search-algorithm

Question

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;
}

Answer 1

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).