2 ms·
Teaching Kids Programming
- ColinWright 6y agoFollowing one of the links, I get to the blog page on algorithmic complexity. There it says: > O(Sqrt(N)) > Checking if a number is a prime number runs at O(Sqrt(N)) because we can just check the possible factors from 2 to Sqrt(N) to see if it can be divided. This is completely at odds with the usual definition, where we talk about the size of an instance in terms of the number of bits needed to specify the instance. So given the instance, the number N, the size of the problem, S, is log_2(N). The number of trial divisions is then proportional to sqrt(N), but we need to express that in terms of S. S=log_2(N), so N=2^S, and sqrt(N)=2^(S/2) ~ (1.4)^S. That means the time taken is proportional to (1.4)^S, and this algorithm is exponential.