Why doesn't Java include the time/space complexity of each function in the javadoc?

Question

Hi I want to know what is the time complexity of the "replaceAll" function of the String class but I can't find any information on it.(http://docs.oracle.com/javase/6/docs/api/java/lang/String.html)

Wouldn't it be better for Java to include the complexities in the Javadoc? I believe it's a very important thing for someone to know.

Apocarp

Answer 1

Most functions have fairly straight forward time complexities. AFAIK, replaceAll is O(n)

IMHO. Nothing beats testing this yourself empirically e.g. with a profiler, because its highly likely that 99% of the methods you use have little to no impact on the performance of your application.

Bregenz

Answer 2

The complexity may be documented if guaranteed. For example, some of the collections classes document complexity guarantees. For example, from HashMap:

This implementation provides constant-time performance for the basic operations (get and put) ...

However, sometimes the complexity is:

• Not guaranteed, and free to change with modifications to the implementation.
• Obviously O(1).

Alard

Answer 3

The javadocs of the Java API specify a general contract of what must be done by each method, not how. Each implementor of the API (say, OpenJDK, Oracle's JDK, etc.) has a certain freedom on how to implement each contract, and that freedom may include making optimizations, even sacrifices in performance. So the javadocs in general don't specify details such as time/complexity of functions, unless it's absolutely necessary for a method to meet certain performance requirements.

Amagasaki

Answer 4

If you're using the space / time complexity of basic operations to drive design decisions, then you're almost certainly doing it wrong.

First build a correct application, then profile it. Then optimize what the profiling process reveals as the bottlenecks.

Lorrettalorri

Answer 5

The general answer is that the complexity typically depends on factors that are too difficult to analyse. This certainly applies for String.replaceAll, where the effective complexity depends critically on the regex string. (A poorly designed regex can make matching veerryyy slow.)

Renfred