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

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]) {
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. Commented Nov 26, 2013 at 21:15