4 ms·
As far as I understand it's runs in expected polynomial time regardless of input. No assumptions on the input necessary. The expectation is over the choice of
by eru 6y ago
As far as I understand it's runs in expected polynomial time regardless of input.
No assumptions on the input necessary.
The expectation is over the choice of random bits created while running the algorithm.