Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ ¹ ² ³ °
 

You are not logged in. #1 20080928 09:31:51
time complexity of divisibilty/primalitySuppose we had a function firstDivisor(unsigned int n) that returns the smallest divisor of n. Observe this number is always prime, and when n is prime, the output is n itself. Last edited by mikau (20080928 09:35:19) A logarithm is just a misspelled algorithm. #2 20080928 10:29:28
Re: time complexity of divisibilty/primalityI'm fairly certain that's not possible. Why did the vector cross the road? It wanted to be normal. #3 20080928 12:21:35
Re: time complexity of divisibilty/primalityGiven a bound on the number (being extremely arbitrary, let's pick 2^32), there are faster ways than the square root of n. Simply construct a list of all primes and use binary search. Or you could use more "fancy" primality tests with strong pseudoprimes, and probably other wacky things that I've never heard about. "In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..." #5 20081119 11:08:57
Re: time complexity of divisibilty/primalityPrime factorization is a nondeterministic polynomial problem (NP). In short, this means that, as far as we know, a computer must have the ability to "magically" guess right answers in order to complete the algorithm in a reasonable (polynomial, or P) time (e.g. always guess an actual divisor first). Specifically, prime factorization is believed to be superpolynomial, or subexponential (taking a time that is somewhere between polynomial and exponential). #6 20081119 12:46:26
Re: time complexity of divisibilty/primality
I think you mean log(n) > ∞ as n > ∞. But even so, can you name a nontrivial problem where that doesn't happen? With almost every problem there is (interesting or not), solutions take longer as n increases, and in an unbounded fashion. Thus, isn't really a criticism for prime factorization, since there are virtually no bounded complexities that typically arise except for constant time. "In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..." #7 20081121 12:54:50
Re: time complexity of divisibilty/primalityAh, my mistake. I was not thinking when I wrote that; the point I was trying to make is untrue. But yes, comparison to existing algorithms is probably the most relevant metric. #8 20081121 17:11:40
Re: time complexity of divisibilty/primality
Typically, yes, but not always. "n" just refers to your metric, which is different for different problems.
You're now using n as the number of digits? And what do you consider to be an operation? "In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..." #9 20081122 12:40:20
Re: time complexity of divisibilty/primalityYes, the choice of "n" is arbitrary; however, in this case, it seems to make more sense for "n" to be the number of digits than the number itself.
Could you clarify your question? I am not really an expert in complexity theory (which I have already amply demonstrated), and thus am not certain exactly what you mean by the term. #10 20081123 04:21:49
Re: time complexity of divisibilty/primality
Certain things don't count as actual "operations" when you are analyzing the complexity of the algorithm. For example, when doing binary search, you constantly divide by 2. But we (typically) don't consider this an operation, the only operation that actually counts is a comparison. That is how we come up with binary search being log(n). There are log(n) comparisons made in the worst case.
Would it not be O(sqrt(10^n))? Unless you're doing something fancier than checking all integers less than sqrt(n) to see if they are a divisor.
How do you get this? If a number has a prime factor, it is at most sqrt(n). We can then divide by the number, and find prime factorization on the new number (since it's primes must be exactly the same). Taking a very high upper bound, let's say we get all the way to the sqrt(n) and we get that 2 is the divisor. In other words, we have to do a lot of searching, and then we only get to divide out by the smallest number. Also, there can be at most log(n) divisors. The complexity would then be: Here, I am taking n to be the number, not the number of digits. If you want to rework this for n being the number of digits, please, by all means. I don't. "In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..." 