2

I'm trying to figure out the complexities of these two functions that I've written but could not understand.def

First, I thought it is supposed be O(N). But it is not clear how many times the loop run because I have no idea how many prime numbers could be found.

def self.find_primes(n)
    primes = []
    total = 0
    i = 2

    while total < n do
      if is_prime i
        primes.push i
        total += 1
      end

      i += 1
    end

    primes
end

In the second function, it is supposed to be O(N/2).

  def self.is_prime n
    (2..n/2).none?{|i| n % i == 0}
  end
2

Estimating the number of iterations in your first function is far from trivial. Luckily, some smart guys have already done the hard work for us several years ago.

It is actually the expected size of the n'th prime, which is the inverse of the so-called prime-counting function. The latter function is known to be approximately x/ln(x), and for the asymptotic behaviour of its inverse, look into this question at mathoverflow. From the accepted answer we see the answer is approximately

   n * ln(n) + n*ln(ln(n)) − n

Note also that the big-O complexity of the first function is not this formula, but the product of this one multiplied by the complexity of the second.

For your second function, note that O(N/2) = O(N). Moreover, one does not need to test all values up to n/2 for checking if n is prime. The square root of n is sufficient for this, so if you implement it that way, you end up with O(sqrt(N)).

1

You can't find the time complexity of your code unless you know how the implementation of none? works. In the worst case, when n is a prime, all values need to be tested, which would be about n/2 operations.

But only? might test all n/2 cases anyway. Or only? might start with the largest value in the range, in which case the average number of steps will be close to n/2.

  • Don't forget big-O is only defined in terms of an upper bound, not in terms of upper and lower. – Doc Brown Jul 1 '18 at 19:18
0

First of all, when we do complexity analysis, we usually consider the number of bits as the size of a number, not its magnitude. When we add a single bit to a variable, the number of possible values doubles, so this nitpick makes your algorithm exponential!

But okay, if we take the magnitude as the size of a number, then you analysis of the second function seems to be correct (making some assumptions on the implementation of none?). Usually, constant factors are ignored, so we would actually call it O(N).

For the first function, O(N) is a good guess, except that it calls the second one, so you have to multiply that in: O(N*N). If you want a more precise analysis, you could actually try to count the number of primes, but that's not necessary: it's an upper bound.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.