3 ms·
It's actually linear. It's searching a key in a linked list O(n), instead of constant access O(1). Still the amplification factor is big enough.
by rurban 7y ago
It's actually linear. It's searching a key in a linked list O(n), instead of constant access O(1). Still the amplification factor is big enough.
- josefx 7y agoCreating 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).