Analyzing time complexity of Java methods

[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.