Depends on the class that implements List and Map. If you use the List class that implements java.util.RandomAccess (i.e. ArrayList), then the call to get (i) is O (1). If this is a LinkedList, it will be O (n).
- Edited to show the following code snippet (since verdy_p is not read well below and likes to remove the tangent): -
// In HashMap.java, line 867, JDK 1.6.0.24, how much more // constant time do we want? public Set<K> keySet() { Set<K> ks = keySet; return (ks != null ? ks : (keySet = new KeySet())); }
- end of editing -
A call to keySet () for most map implementations will be constant.
Regarding passing keySet () If you use a Map-backed Map implementation (like HashMap), keySet () relies on entrySet (), which returns the internal iterator supported by the array. So, the iteration of keySet () is O (n).
I would also suggest that this applies to most (if not all) map implementations that are supported by arrays.
For implementations of SortedMap (for example, TreeMap), the iteration on its keys will be akin to iterating through the tree from the lowest to the maximum. This is equivalent to a failed binary search, which is O (n).
Both cases look like O (n). If you use Eclipse, you can look at the code that implements java classes and better understand their complexity.
For classes under java.util.concurrent (e.g. ConcurrentHashMap) you will have to take other considerations to determine how expensive they are.
To expand the bit, if you use a linked list, list.get (i) .keyset () will be O (n). With an ArrayList, this will be O (1). Moving the key set will depend on whether you are using a map with an array (HashMap) or SortedMap (TreeMap). In both cases, the move will be O (n), and the first will be much faster than later, since traversing the array will always be faster than moving along pointers (or links in this particular case of Java).
Now, if you take both list.get (i) .keySet () and iterate over the set, with an implementation of a linked list , which will be O (n ^ 2). Therefore, instead of doing list.get (i) .keySet (), you should use an iterator (see below pseudocode , for clarity, it excludes the general syntax)
This is O (n ^ 2) for lists that do not implement java.util.RandomAccess (e.g. LinkedList):
for( int i = 0; i < list.size(); i++ ) { Set keySet = list.get(i).keySet(); for( Integer key : keySet.iterator() ) { ... stuff (assuming constant time) ... } }
This is O (n) for the same type of List implementations:
for( Map m : list.iterator() ) { for( Integer key : m.keySet() ) { ... stuff (assuming constant time) ... } }