3 ms·
I don't understand how this is O(n). You have to go through the set once to select each word and replace a b with o, then you have to go through the set again t
by YeGoblynQueenne 6y ago
I don't understand how this is O(n). You have to go through the set once to select each word and replace a b with o, then you have to go through the set again to search for the new word resulting from the replacement.
That is, if Ws is the set of 5-letter words we want the set Rs = {w: w ∈ Ws, w.replace(b,o) ∈ Ws}. You can see that that's an O(n²) operation (each ∈ is an iteration over Ws).
jayd16 proposed omitting every word that has a b in it from the "search space". I take this to mean, in practice, that we start by initialising a set Ss = {w: w ∈ Ws, b ∉ w}. Then Rs = {w: w ∈ Ws, w.replace(b,o) ∈ Ss} and the time complexity is O(|Ws||Ss|) which is again O(n²) in the worst case (where Ws = Ss). Note also that some words in Ws may have more than one b and since we are only replacing "a b" (i.e. one b) we may remove valid words this way.
In any case, I don't see an obvious way to do this in O(n). Maybe I'm not thinking straight though, it's way past bed time.
- raldi 6y agoYou agree that set lookup is O(1) and we need to do it N times, right?
- YeGoblynQueenne 6y agoYep, my mistake. I was thinking of list lookups. I should have gone to bed :) In any case, even if it was O(n²) that's a polynomial time complexity and I don't see why BDDs are needed.