Блог пользователя Qualified

What is the time complexity of this function?
Автор Qualified, 4 года назад, По-английски

I just copied the Miller-Rabin algorithm for primality testing from E-Maxx Algorithms. I wanted to know the time complexity of that function. Here is the link to that article.

  • Проголосовать: нравится
  • -28
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Fun fact: the latter implementation is bounded by a constant, and so is O(1).

Seriously though, why don't you at least begin reading the code to get the answer, and ask a concrete question once you have it? It's just a few nested loops anyway, no rocket science.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Perhaps this impl makes it clearer: link.

Hint
→ Ответить