This week's book giveaway is in the OCAJP 8 forum. We're giving away four copies of OCA Java SE 8 Programmer I Study Guide and have Edward Finegan & Robert Liguori on-line! See this thread for details.
Constant time is one example of a time complexity class. Here are several example classes:
These classes say something about how scalable a function is. 'n' stands for how big the problem is. For collections, 'n' usually means how big the structure you're performing the function on currently is. A function that operates within constant time will require a constant amount of time to finish, regardless of how big the problem is. Think of an ArrayList. ArrayLists are random access, so the get() method operates within constant time.
A function that calculates the sum of all numbers in a list operates within linear time, because it has to traverse every element. So the bigger the list, the more time it needs. If the list is twice as big, the amount of time will (roughly) be twice as much.
Let's take a look at the contains() method of TreeSet. To determine whether an element is in the tree, it checks whether the root element is the same as the requested element. If not, it goes to the sub-tree that's smaller or larger than the root, depending on whether the requested element is smaller or larger than the root. This process continues until the element has been found, or the bottom of the tree has been reached.
The method doesn't need to traverse every element, but it does take longer for larger trees. It operates within logarithmic time.
The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.
Is 'HashSet' the answer? It is not sorted and allows unique objects. Addition/removal/retrieval of any object within this set deals with first finding out the hash code and then locating the correct object from the ones having the same hash code. This process is independent of total number of elements. Please let me know if I am thinking in the right direction.