Big-o обозначение этого псевдокода

Question

Я считаю, что это O (n), потому что нет вложенных циклов или деления / умножения. Я прав?

i <-  0
count <-  0
while(i<n)
 x  <- random()
 y <-  random()
 if (x^2 + y^2 <= 1)
   count   count+1
 i <-  i + 1

сделано пи <- 4 * кол / н </p>

Answer 1

Давайте посмотрим на все утверждения, на этот раз добавив несколько меток в скобках

[1] i <- 0
[2] count <- 0
[3] while(i < n)
  [3.1] x <- random()
  [3.2] y <- random()
  [3.3] if (x^2 + y^2 <= 1)
     [3.3.1] count <- count + 1
  [3.4] i <-  i + 1

Теперь давайте посчитаем сложность каждого из утверждений:

[1] O(1)
[2] O(1)
[3] n times
  [3.1] O(1)
  [3.2] O(1)
  [3.3] O(1)
     [3.3.1] O(1)
  [3.4] O(1)

Итак, общая сложность составляет

O(1) + O(1) + n * 4 * O(1) = O(n)

Answer 2

Это O (n), потому что цикл while выполняется n раз.