CODEWITHSUNDEEP
rubyalgorithmbig-o
amone
amone

Reputation: 3862

What is the complexity of find and checking prime numbers?

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

Upvotes: 1

Views: 68

Answers (1)

jesellers
jesellers

Reputation: 36

The outer loop is O(N). The inner loop is O(N/2), which is just O(N). Therefore, the function as a whole is O(N^2). Knowing the number of primes that could be found doesn't affect time complexity, since time complexity is a function of N, i.e., it increases or decreases with N.

Upvotes: 1

Related Questions