4 ms·
Sorting D is a one time operation of n log n, so the overall complexity is n log n + n * m, which reduces to O(n * m) where n is number of words in D and m is l
by panda88888 8y ago
Sorting D is a one time operation of n log n, so the overall complexity is n log n + n * m, which reduces to O(n * m) where n is number of words in D and m is length of S.
- ascar 8y agoYou are right, I was off. On another note: I absolutely do not understand why we substitute the international mathematical symbol for cardinality (|A|) with variables we have to explain. Computer science has a math background, so we all know set theory. At least I also learned using cardinality with Big O notation in university. But for some reason industry prefers to use variables here.
- jldugger 8y agoI'm not sure my math classes ever actually mentioned that particular notation. I agree it's more elegant to formalize the analysis, but it's not particularly elegant on the webpage -- the kerning feels off.