How conservative is your analysis? Is it whole program? Do you look at the class library? What's the largest size of program it handles in a reasonable amount of time?
1. Very conservative (I hope). As to exactly what this means, the specs are here: http://robmoffat.github.io/pure4j/concordion/org/pure4j/test...
2. Not the whole program, but "islands of purity". i.e. classes or hierarchies of classes which are annotated with @Pure/@ImmutableValue/@MutableUnshared (see above for what these mean, exactly).
3. At compile time, it builds a model of your software by analysing the byte-code. It should run in linear time I guess but I haven't tried it on any huge codebases yet. At runtime, the performance will be heavily dependent on the performance of the Clojure collections that I've imported.