Finding which strings in a set of strings have a certain prefix - can it be smaller than O(number of strings*length of prefix)

Question

If I have a set of words and need to return which of them start with a certain prefix, can that complexity be less than O(n*d), where n is the number of words and d is the prefix. I'm asking because of this video: https://www.youtube.com/watch?v=QGVCnjXmrNg (1:20 starts discussing the solution), where it says it can be lowered through using a trie with all of the words, but I think the creation of the trie would take O(n*t) complexity, where t is the average length of the words. Assume that all words will be at least as long as d (any word which has length smaller than d is disregarded immediately in the solution below, but is still considered during the creation of the trie in the video).

My idea for the solution is the simple one: go through each word and check if it starts with the same prefix. If it does, add it to the list of words which start with that prefix, otherwise don't. The reason I think this is the best solution possible in terms of worst-case complexity is as follows: if we skip even one character or one string, we may return the wrong answer. This is the minimum input that is to be considered and in any other case, it is also considered (for example, in the solution that input is considered during the creation of the trie).

Example javascript code:

function solve(prefix, words) {
    //startsWith has worst-case complexity O(d) where d is the length of the prefix
    function startsWith(word, prefix) {
        //this doesn't change worst-case complexity but means that the only disregardable input is disregarded
        if (prefix.length > word.length) return false;

        for (let i = 0; i < prefix.length; i++) {
            if (prefix[i] !== word[i]) {
                return false;
            }
        }

        return true;
    }

    const wordsArray = [];

    //since there are n (n is the length of the words array) and every iteration has worst-case complexity O(d),
    // we have a worst-case complexity of O(n*d)
    for (let i = 0; i < words.length; i++) {
        if (startsWith(words[i], prefix)) {
            wordsArray.push(words[i]);
        }
    }

    return wordsArray;
}

console.log(solve("do", ["dog", "dark", "cat", "door", "dodge"]));

I'm asking that because in the video it was mentioned that it can be faster than O(n*d), but I believe the solution was wrongly analyzed. I, however, am just a hobbyist and feel like it is more likely I'm missing something here.

Answer 1

In the worst case, it has to be $n \cdot d$: You must check $d$ symbols of each of the $n$ strings to confirm they all start with the prefix, if you leave any out it might be different. This is essentially an adversarial argument.

You certainly can speed it up for non-matching strings, like comparing lengths, just check some positions to rule out prefixes. If the strings are random, checking just the first symbol will weed out all but a fraction of the strings (like the program you show does, bailing out early).

If you assume random strings over an alphabet of $m$ symbols, they will agree with the first $k$ symbols of your needle (which you are looking for in the haystack) $1/m^k$ of the times. The number of checks to do for each string will then be on average:

$\begin{align*} c &= 1 + \sum_{2 \le k \le d} \frac{k}{m^k} \end{align*}$

(you do $1$ check regardless, then $k$ more checks if $k$ symbols match).

To compute this sum, note that:

$\begin{align*} f(z) &= \sum_{0 \le k \le d} \frac{z^k}{m^k} \\ &= \frac{1 - z^{k + 1} / m^{k + 1}}{1 - z / m} \\ &= \frac{m^{k + 1} - z^{k + 1}}{m^{k + 1} - z m^k} \\ f'(z) &= \sum_{0 \le k \le d} \frac{k z^{k - 1}}{m^k} \\ f'(1) &= \sum_{0 \le k \le d} \frac{k}{m^k} \\ &= \frac{m^{d + 1} - (d + 1) m + d}{m^d (m - 1)^2} \\ c &= 1 + f'(1) \\ &= 1 + \frac{m^{d + 1} - (d + 1) m + d}{m^d (m - 1)^2} \end{align*}$

Thus the number of symbol comparisons for one string is approximately $(m + 1) / m$, as you'd suspect.