3 ms·
Why is the running time of the attacked python process exponential? I would expect quadratic.
by ErikCorry 7y ago
Why is the running time of the attacked python process exponential? I would expect quadratic.
- petters 7y agoI think that the author is mistaken or careless when making that particular statement.
- 6gvONxR4sf7o 7y agoIt's probably using the colloquial version of the word (which I hate). "Exponentially" = "hugely, but I want to sound technical." Or the still frustrating but more acceptable "exponentially" = "by orders of magnitude."
- sansnomme 7y agoMaybe OP should use P and NP instead.
- mehrdadn 7y agoWas wondering the same thing. My guess is he just meant 1000 -> 100 -> 10 -> 1 -> exponential.
- rurban 7y agoIt'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).