5 ms·

Ooh, what's the time and space complexity of `primes`?

by millstone 7y ago

Rerarom 7y ago
Primes is in p
- OscarCunningham 7y ago
  Returning the nth prime is not known to be in P.
  - Rerarom 7y ago
    I know, I was being silly.
cjfd 7y ago
Clearly much worse than the original solution. Basically, a nested sequence of filters is built, one to filter out multiples of each prime number. One way in which the complexity of this is bad is that if you want prime numbers < N you only need to filter out primes smaller than sqrt(N). It is telling that the first solution contains an sqrt but not the second one.... These kind of functional solutions are very cute mathematically, but... I once wrote this way of generating an infinite list of primes in unlambda. That was kind of interesting to do.
- merijnv 7y ago
  > One way in which the complexity of this is bad is that if you want prime numbers < N you only need to filter out primes smaller than sqrt(N). It is telling that the first solution contains an sqrt but not the second one.... That's not really true, though, because that filter is applied lazily, so it only get evaluated up until the Nth prime and no further.
merijnv 7y ago
I'd say O(n) for both. The generated list only contains primes, so that's straightforward linear. Then there is the recursive sieving, which adds an additional pass over the sieve list for every prime we've found so far, we need keep the computation of each pass in memory, so that's some additional memory that's also linear. The time complexity is less obvious, each prime adds an additional pass to evaluate, so that seems linear, but each new pass only applies to a list that already had all the previous passes filtered out, so that's not technically linear, but I find it hard to determine how much it actually is.
- cjfd 7y ago
  clearly O(n^2) for time. Well, perhaps O(n^2/log n) or something, but that is not much different. The thing is, every prime p gets passed through a filter that filters multiples of primes p' for all p' < p.
  - merijnv 7y ago
    > The thing is, every prime p gets passed through a filter that filters multiples of primes p' for all p' < p But the filter for multiples of 3 only sees the values that weren't already filtered by 2. So if we have N filters we don't evaluate all N filters for each value. The 2 is applied to everything, the 3 filter is only applied to things that are not multiples of 2, the 5 filter is only applied to things that aren't multiple of 2 and 3, etc. That doesn't sound very quadratic to me.
    - cjfd 7y ago
      The thing is that the prime numbers have to go through all of the filters. Although the prime numbers are a minority among the numbers they are not a very small minority. In fact, a random number N has about a probability of 1/log(N) to be prime. So that could reduce N^2 to maybe N^2/log(N) but not any further. So I suppose the complexity actually is somewhere between N^2 and N^2/log(N), but that is not much less than N^2. The trick of only checking primes smaller than sqrt(N) reduces the complexity to N^1.5, also maybe involving some division by log(N), but that is actually an improvement in the exponent.
deleted 7y ago
[deleted]

Ooh, what's the time and space complexity of `primes`?

Rerarom 7y ago

Primes is in p

OscarCunningham 7y ago
Returning the nth prime is not known to be in P.
- Rerarom 7y ago
  I know, I was being silly.

cjfd 7y ago

Clearly much worse than the original solution. Basically, a nested sequence of filters is built, one to filter out multiples of each prime number. One way in which the complexity of this is bad is that if you want prime numbers < N you only need to filter out primes smaller than sqrt(N). It is telling that the first solution contains an sqrt but not the second one.... These kind of functional solutions are very cute mathematically, but... I once wrote this way of generating an infinite list of primes in unlambda. That was kind of interesting to do.

merijnv 7y ago
> One way in which the complexity of this is bad is that if you want prime numbers < N you only need to filter out primes smaller than sqrt(N). It is telling that the first solution contains an sqrt but not the second one.... That's not really true, though, because that filter is applied lazily, so it only get evaluated up until the Nth prime and no further.

merijnv 7y ago

I'd say O(n) for both. The generated list only contains primes, so that's straightforward linear. Then there is the recursive sieving, which adds an additional pass over the sieve list for every prime we've found so far, we need keep the computation of each pass in memory, so that's some additional memory that's also linear. The time complexity is less obvious, each prime adds an additional pass to evaluate, so that seems linear, but each new pass only applies to a list that already had all the previous passes filtered out, so that's not technically linear, but I find it hard to determine how much it actually is.

cjfd 7y ago
clearly O(n^2) for time. Well, perhaps O(n^2/log n) or something, but that is not much different. The thing is, every prime p gets passed through a filter that filters multiples of primes p' for all p' < p.
- merijnv 7y ago
  > The thing is, every prime p gets passed through a filter that filters multiples of primes p' for all p' < p But the filter for multiples of 3 only sees the values that weren't already filtered by 2. So if we have N filters we don't evaluate all N filters for each value. The 2 is applied to everything, the 3 filter is only applied to things that are not multiples of 2, the 5 filter is only applied to things that aren't multiple of 2 and 3, etc. That doesn't sound very quadratic to me.
  - cjfd 7y ago
    The thing is that the prime numbers have to go through all of the filters. Although the prime numbers are a minority among the numbers they are not a very small minority. In fact, a random number N has about a probability of 1/log(N) to be prime. So that could reduce N^2 to maybe N^2/log(N) but not any further. So I suppose the complexity actually is somewhere between N^2 and N^2/log(N), but that is not much less than N^2. The trick of only checking primes smaller than sqrt(N) reduces the complexity to N^1.5, also maybe involving some division by log(N), but that is actually an improvement in the exponent.

deleted 7y ago

[deleted]