4 ms·
Creating the dict performs n * O(n) searches in total, so wouldn't it be O(n^2) ?
by josefx 7y ago
Creating the dict performs n * O(n) searches in total, so wouldn't it be O(n^2) ?
- mehrdadn 7y agoDepends on if "it" refers to the creation of the dict or to lookups thereafter...
- josefx 7y agoI mean the attack as a whole. I think having a linear lookup alone wouldn't be as problematic if it didn't turn the creation of the dictionary itself quadratic. The attack wouldn't scale near as well if it ran in O(n).