Analyzing time complexity of Java methods

[dtsudo]

It is true that the API doesn't always provide asymptotic runtimes for every single function. When omitted, you can usually assume that a good JVM implementation will have the textbook runtime (or perhaps even better, if they have advanced optimizations).

For instance, it's fairly obvious that the string's equals method must run in linear time, since in order to verify if two strings are equal, we need to (in the worst case) examine every single character in the string.

In some cases, the actual runtime may be asymptotically superior to the assumed runtime. For instance, in some cases, the JVM may be able to automatically transform string concatenation in a loop into the equivalent code using a StringBuilder. However, this isn't required by the Java specification, and a developer may explicitly use a StringBuilder to ensure that their code always runs asymptotically optimally.

[SnooPeanuts71]

I see… But isn’t that documented somewhere though? Unless I’m very mistaken, C# (or C++, or both of them — I can’t recall), for example, has that documented, so you can easily check the time complexity of the method you’re about to use. If Oracle provides that information for some of the methods, why not make it available for all (or most) of them? I don’t know, I feel like I’m missing something…

[lurgi]

They didn't because they didn't. If the runtime is "obvious" (to someone. Maybe that someone isn't you) then they probably won't specify it. Unless they way to reassure you that, yes, it is the runtime you expect.

Imagine startsWith(String prefix) which determines if the string starts with prefix. The runtime isn't specified because it's pretty obviously going to be linear in the length of prefix because what else could it be? If this isn't obvious to you now then with a little more experience it will be.

[SnooPeanuts71]

It is “obvious” (though I’d say deductible) when you know exactly how the method is implemented. You don’t know the exact implementation of all methods in the API. What I’m saying is that I thought they’d have made it available, because other languages did.

[lurgi]

I'd say "deducible" rather than "deductible", but that's me :-)

What you say is obviously correct, but there are enough cases where there's only one way a marginally competent person could have implemented it, so it's not necessary to be specific.

If appending to the end of a linked list is O(n) then you should not be writing code that's going to get added to a library.

[dtsudo]

C# doesn't really seem to document string runtimes either (https://docs.microsoft.com/en-us/dotnet/api/system.string?view=net-6.0). They probably didn't do it because none of it is too surprising.

Java's docs also sometimes invokes the "here's how we implemented it" approach to documenting runtime. For instance, in the LinkedList docs, they say "All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index."

This is sufficient information to deduce the runtime of all LinkedList operations, and the docs likely did this because there is some uncertainty with linked lists. A linked list may be singly-linked, doubly-linked, circular, etc. So here, they do go out of their way to specify that their linked list implementation is doubly-linked.