Qualified's blog

What is the time complexity of this function?
By Qualified, 4 years ago, In English

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.

  • Vote: I like it
  • -28
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Perhaps this impl makes it clearer: link.

Hint
→ Reply