3 ms·
No, it clearly says two memory accesses per character. "At worst" calculation is just calculating the worst case (string not found) where it has to scan the wh
by kyberias 6y ago
No, it clearly says two memory accesses per character.
"At worst" calculation is just calculating the worst case (string not found) where it has to scan the whole string and... access each byte twice.
It doesn't matter whether we have a worst case or not. They claim two memory accesses per character.
- klodolph 6y ago> It doesn't matter whether we have a worst case or not. They claim two memory accesses per character. Yes, a worst case of two memory accesses per character. This is obvious, no? When people analyze algorithm runtime it is not always explicitly stated whether the author is doing worst-case or average-case analysis. So, as a reader, you sometimes have to figure it out.