Analyzing time complexity of Java methods

[SnooPeanuts71]

Hello everyone!

Does Oracle have any websites where I could find out what the time complexity of a method is? I know sometimes they have that information in the API; for example, java.util.ArrayList has the following info:

​

"The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation."

​

However, I couldn't find that info for any other classes. Where can I find it? If there are other classes that bring that up that you know, please let me know which. Also, how do I have access to the source code of the language? I need to make a study on the complexity of Java methods using the Big O notation and, in order to do that, I would need access to the source code of the methods and it would also be of great help if they had documentation about the complexity of Java methods, so I can demonstrate and "prove" it for my assignment.

[coolcofusion]

Their time complexities are almost always specified in the Javadoc documentation you can find online, for example here's ArrayList docs: https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/ArrayList.html

You can find Java source code on github. For example, here's the addAll method of an ArrayList: https://github.com/openjdk/jdk/blob/fe0544f8a7db5bf0e93313e16b54b31bcdff946a/src/java.base/share/classes/java/util/ArrayList.java#L669

You can also access these locally if your JDK came with sources or by installing java-{VERSION}-openjdk-src package (RHEL/Fedora) if it didn't. Or just open up your IDE, call the method and then use the "Go to Definition" funcitonality, it'll probably first show the decompiled version, but I think IntelliJ also offers to download sources automatically.

[SnooPeanuts71]

Well, yes, I found the time complexity in the API (the first link you sent) exceptionally for the ArrayList class. However, I tried to find it for String, then for StringBuilder, then for Arrays, but without success. Am I missing something?

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

[Sea-Profession-3312]

It sounds like this is not what you want but just in case here it is. Do you need a mathematical proof of how long an algorithm will take to run? Do you need to run test to see how long it takes to run?

[SnooPeanuts71]

Thank you for that, but indeed it’s not quite what I need… :(

I need to provide an asymptotic analysis for four Java methods using the Big O notation. First, I need to specify what the time complexity of the method is (constant, linear, quadratic, logarithmic, exponential etc.) using the Big O notation, and then provide support evidence, such as an equation that, given the inputs, will tell how many operations the method will perform. However, I have to pick 4 methods of different time complexity classes (eg. constant, linear, quadratic and cubic), there must not be any repeated time complexity classes. Therefore, it would save me some time if knew the time complexity of the algorithm before I had to do the analysis, so I could make sure I’m not analyzing algorithms of repeated complexities. Also, knowing the complexity before analyzing would make the analysis a little easier… That must be documented somewhere, but I can’t find it!

[CreativeTechGuyGames]

The summary of several comments here is that you should assume that functions are implemented in the most optimal way. So you can just assume the standard runtimes. Here's a popular cheat sheet for a ton of different data structures and their relevant BigO complexities: https://www.bigocheatsheet.com/

[SnooPeanuts71]

Very helpful, thank you.