3 ms·
Depends what you mean by larger. The example that occurs to me is the priblem of determining whether or not an integer is prime. This can be done relatively qui
by mjcohen 3y ago
Depends what you mean by larger. The example that occurs to me is the priblem of determining whether or not an integer is prime. This can be done relatively quickly for numbers of the form 2^p-1 where p is prime, but would take much longer for a much smaller prime not of this form.
- Nevermark 3y agoThose would be effectively different problems. Adding the constraint of only needing to classify a particular form of prime will always result in an algorithm of equal or lesser complexity order.