CODEWITHSUNDEEP
algorithmbig-o
Adam
Adam

Reputation: 365

Complexity of this prime number search algorithm

So I'm learning about Big O notation at the moment and I'm not sure how to work out what the Big O is of my following (deliberately inefficient) algorithm:

def getPrimes(n):

primes = [2]    

for i in range(3, n+1):
    remainder = True
    for j in primes:
        if(i % j == 0):
            remainder = False
    if(remainder == True):
        primes.append(i)
return primes

The amount of times the inner for loop will run will increase depending on how many items are inside the list, 'primes'. So how does that affect working out what the Big O is, if at all?

Upvotes: 1

Views: 234

Answers (2)

Paul Hankin
Paul Hankin

Reputation: 58320

Each i is tested against all primes less than i. Thus, the total amount of work done is:

sum(i=3..n)pi(i)

(where pi(i) is the number of primes less than i).

pi(n) is Theta(n/log n), so the amount of work done is in the same complexity class as:

sum(i=3..n)i/log(i)

I don't think there's any good approximation for this, but it's better than O(n^2) but not by much since log(i) grows slowly compared to i.

Upvotes: 1

MBo
MBo

Reputation: 80232

Check for Pi(n) function. It's approximation is n/ln(n).
Overall algorithm (a kind of Sieve of Eratosthenes implementation) complexity is evaluated as O(n(loglog(n))

Upvotes: 1

Related Questions