Content deleted Content added
→Complexity: e^log(x) = x — O, RLY? — YA, RLY! |
m →Complexity: Date maintenance tags and general fixes |
||
Line 31:
==Complexity==
Pollard gives the time complexity of the algorithm as <math>{\scriptstyle O(\sqrt{b-a})}</math>, based on a probabilistic argument which follows from the assumption that ''f'' acts pseudorandomly. Note that when the size of the set {''a'', …, ''b''} to be searched is measured in [[bits]], as is normal in [[complexity theory]], the set has size log(''b'' − ''a''), and so the algorithm's complexity is <math>{\scriptstyle O(\sqrt{b-a}) = O(e^{\frac{1}{2}\log(b-a)})}</math>, which is exponential in the problem size{{
==Naming==
| |||