1

I have been using the Java documentation for OpenJDK 1.7, but I am not seeing a lot of information on Big-Oh notation in terms of complexities of operations between different container types, which is making it harder to know which is the most performance collection to use for my task at hand; for example, implementing a stack or a queue.

I have been using an ArrayDeque for both just following my C++ instincts. The basics are there, such as ArrayList is faster than LinkedList, but there doesn't seem to be a consistent section for this. In C++ documentation, there is a section like the one below. Any Javadoc references that speak about complexities between containers would be helpful.

C++ example: http://en.cppreference.com/w/cpp/container/unordered_set/equal_range

Complexity

Average case constant, worst case linear in the size of the container.

Java Example: Embedded in the ArrayList documentation I found the following

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.

Makoto
  • 104,088
  • 27
  • 192
  • 230
bjackfly
  • 3,236
  • 2
  • 25
  • 38
  • 4
    I'm not sure I understand...the Javadoc header section before the relevant collections seem to do a good job of explaining the expected runtime and behavior of the collection you're using. Were you looking for something more specific to Java, or related to collection types in general? – Makoto Aug 18 '13 at 22:49
  • Thanks Makoto, I was trying to figure out how to format that as you did. I think I got it now, block quote. Thanks for this. – bjackfly Aug 18 '13 at 22:50
  • Maybe I am just looking in the wrong place? I have a downloaded version of the javadoc and for instance will just look at the LinkedList class which doesn't tell me much about Big-O but maybe I am not looking in the right place. I just search for the collection in the left pane and click the link. – bjackfly Aug 18 '13 at 22:53
  • It is the same as http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html Although the other answer does have some links like I have seen the big o cheat sheet but it is not specific to java definitely java vector is it's own unique item – bjackfly Aug 18 '13 at 22:59
  • 1
    From the ArrayList javadocs you link to: *"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.*". Every one of those docs has a paragraph on the performance. – Brian Roach Aug 18 '13 at 23:03
  • Ok, I see that section you mentioned I thought for each method on the collection it might break down best worst and avg performance. In this case it says it should perform like a doubly linked list but it doesn't give any direct language on Big o for that. Again I might be missing something here. – bjackfly Aug 18 '13 at 23:18
  • Don't take Big-O too literal unless the N is actually large enough to matter. If performance matters, measure it for your use-case. – zapl Aug 18 '13 at 23:53
  • 1
    The [Collections](http://docs.oracle.com/javase/tutorial/collections/TOC.html) trail by Josh Bloch (who authored most the Collections API in Java) has a bit of information on that in the implementations section. He also describes the sorting and searching algorithms as well as their complexities. Of course, it's not tabulated or anything, you really have to read through it to get the information you're looking for sadly. And if all else fails, the Javadoc usually has what you're looking for. – sgbj Aug 19 '13 at 02:17

0 Answers0