3 ms·
Isn't it O(log n)? I guess computationally it may blow up if you are doing a significant number of operations.
by dangoldin 17y ago
Isn't it O(log n)? I guess computationally it may blow up if you are doing a significant number of operations.
- swolchok 17y agoIt depends on how you measure n. The O(log^{6+\epsilon}(n)) quote on Wikipedia is for n being the number to be tested. This is "cheating"; inputs to an algorithm need to be measured by their length, and numbers are exponential in their length (i.e., the length of the number n is order log n for "reasonable encodings"). As an example, the knapsack problem with n objects and weight W is solvable in O(n*W) time, but it's known to be NP-hard. This doesn't prove P=NP, because W is exponential in its length. This is called a pseudopolynomial algorithm.
- dangoldin 17y agoAh got it. Thanks for the clarification. Coincidental too since I just read about the AKS algorithm on Terrence Tao's blog. http://terrytao.wordpress.com/2009/08/11/the-aks-primality-test/ http://terrytao.wordpress.com/2009/08/11/the-aks-primality-t...