В чем сложность поиска и проверки простых чисел?

Question

Я пытаюсь выяснить сложности этих двух функций, которые я написал, но не смог понять .def

Сначала я подумал, что это должно быть O(N). Но не ясно, сколько раз цикл выполняется, потому что я не знаю, сколько простых чисел можно найти.

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

Во второй функции она должна быть O(N/2).

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

Answer 1

Внешний цикл O (N). Внутренний цикл O (N / 2), который просто O (N). Следовательно, функция в целом есть O (N ^ 2). Знание количества простых чисел, которые могут быть найдены, не влияет на сложность времени, поскольку сложность времени является функцией N, то есть она увеличивается или уменьшается с N.