Running time of an algorithm

Question

def isprime(n):
   # 0 and 1 are not prime
   if n < 2:
    return False
   # 2 is prime
   if n == 2:
       return True    
   # even numbers are not prime
   if n % 2 == 0:
       return False
   # test if any odd number between 3 and the square root of n divides n
   # (it suffices to only go up to the square root)
   for i in range(3, int(n**0.5) + 1, 2):
       if n % i == 0:
           return False
   return True

Why is the running time of this algorithm n (square root of n)? One could explain how to calculate?

Answer 1

Algorithm complexity is given by the amount of steps needed to perform something based on the number of items that need to be evaluated, which has been agreed to call n. Algorithm complexity is usually measured and represented by the so-called Big O notation.

So if no matter the amount of items an operation always needs to 1 step the complexity is said 1 or constant (example is access to an array). Showing a loop:

for i in range(1, 1, 1):

If you need n steps to evaluate n items, so the complexity is n or linear (example is to list the items of a array). The noose would look like this:

for i in range(1, n, 1):

And if you can do that by breaking into fractions, usually 2, the complexity is logarithmic, so called log n because it uses a logarithmic function to calculate how many steps they need, ie if you have about 1000 items it will take 10 steps (example are operations on binary tree structures):

for i in range(1, log(n, 2), 1):

I could see that there is always a formula from the simplest to the most complex to calculate it. And the formula can be very complex.

In your case the formula is given in the code. The number of items that will be evaluated is N up to 0.5, so it’s simple to find complexity (see next paragraph that has a catch). The loop will perform the amount of times the result of this formula, equal to the examples cited above. Then:

for i in range(3, int(n ** 0.5) + 1, 2):

I put in the Github for future reference.

But note that there are two extra details in this calculation. He is picking up an extra item. So the whole formula has to be consider whether you want accuracy in number. In most cases it will make little different real, but math ignore the + 1 is a mistake. Another more serious problem is that it is not skipping 1 to 1, it is skipping 2 to 2, so the complexity of the algorithm is N raised in the middle, plus 1 and all that divided by 2 ((N ** 0.5 + 1) / 2). By the way this formula is very close to the logarithmic based 2. And note that in some cases N very low nor will perform anything.

Note that this is the worst case, can have me in the steps in many cases.

Maybe you’re confused by the use of range() that has an initial value, a value to where it should go (the end) and how much to jump.