CODEWITHSUNDEEP
rubyregexbig-otime-complexityprimes
Alston
Alston

Reputation: 1226

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

This line of ruby code detects prime numbers (awesome!). 

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

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

I'm curious about it's performance in the manner of BIG-O notation. Anyone help?

Upvotes: 7

Views: 671

Answers (1)

tom
tom

Reputation: 22979

From empirical data it appears to be O(n2).

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

Graph showing time taken to check if a number is prime.

The blue dots are the recorded times and the orange line is y = 2.9e-9 * x^2. The line fits the data perfectly, indicating that the complexity is O(n2).

This is to be expected since the regular expression checks all possible divisors to see if any of them occurs a whole number of times in the string.

Upvotes: 6

Related Questions