5

Question pretty much says it all. Specifically, I would like the Big-O of all the methods within a structure, aside from the usual. The docs say very little about this.

Addennum

For those who are voting to close, I am not interested in the basic add, remove, iterator, etc Those sources are fine for regularly used methods, but I am more interested in the algorithmic efficiency of the rest of the pile.

For example, what is the efficiency of TreeMap.keySet()?

Brian Tompsett - 汤莱恩
  • 5,438
  • 68
  • 55
  • 126
Jason
  • 10,995
  • 20
  • 83
  • 176

4 Answers4

1

Java Collections Algorithm Efficiencies: Source

ArrayList

  • get, set: O(1)
  • add, remove: O(n)
  • contains, indexOf: O(n)

HashMap

  • get, put, remove, containsKey: O(1)

HashSet

  • add, remove, contains: O(1)

LinkedHashSet

  • add, remove, contains: O(1)

LinkedList

  • get, set, add, remove (from either end): O(1)
  • get, set, add, remove (from index): O(n)
  • contains, indexOf: O(n)

PriorityQueue

  • peek: O(1)
  • add, remove: O(logn)

TreeMap

  • remove, get, put, containsKey: O(logn)

TreeSet

  • add, remove, contains: O(logn)
nem035
  • 33,305
  • 5
  • 80
  • 94
  • When you remove an element in the array list, don't you have to step down the elements with the highest index? – EliuX Nov 29 '18 at 00:49
0

I would review the standard Big-O information about algorithms in Introduction_to_Algorithms.

Michael Shopsin
  • 1,965
  • 2
  • 24
  • 39
0

I am not sure is there a spreadsheet or other list, but you can get this information in docs for every structure, for example TreeSet:

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

Andrey
  • 57,904
  • 11
  • 115
  • 158
0

There really cannot be. Each JVM can have it's own runtime, with its own implementations. A few methods have specified O() characteristics, but the rest are whatever Sun, or Oracle, or IBM, or Apple, or Azul, does.

bmargulies
  • 94,623
  • 39
  • 172
  • 299
  • so why here: http://download.oracle.com/javase/6/docs/api/java/util/TreeSet.html is said "This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains)." JVM and classes implementation is different thing. – Andrey Nov 04 '10 at 19:59
  • Are you sure that everybody who makes a JVM also reimplements all the JRE libraries? – darioo Nov 04 '10 at 20:02
  • @Anrey, I said, 'a few methods'. That's an example. @darioo, no of course not. But you can't predict. – bmargulies Nov 04 '10 at 20:51
  • Maybee it is true that some JVM don't have implementations that work in "guaranteed log(n) time cost for the basic operations (add, remove and contains).", but then this would be a bug. If the JavaDoc says it works in O(foo), then you can expect it to run at least in O(foo). If not write you should write a bug report. – iuiz Nov 22 '10 at 13:11