Regex - What is the complexity of this regular expression for primes?

Question

This line of ruby ​​code detects primes (awesome!).

("1" * n) !~ /^1?$|^(11+?)\1+$/ # where n is a positive integer 

Details are explained in this blog post http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/

I am curious that this is performance in the form of BIG-O notation. Anyone help?

Answer 1

From empirical data, it looks like O (n ² ) .

I ran Ruby code on every 100th of the first 10,000 primes. Here are the results:

The blue dots are the recorded time, and the orange is y = 2.9e-9 * x^2 . The string matches the data perfectly, which means the complexity is O (n ² ).

This is to be expected, as the regular expression checks all possible divisors to see if any of them are integers in the string.