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.
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes What does constant-time performance mean. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of OCA Java SE 8 Programmer I Study Guide this week in the OCAJP 8 forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "What does constant-time performance mean. " Watch "What does constant-time performance mean. " New topic

What does constant-time performance mean.

O. Ziggy
Ranch Hand

Joined: Oct 02, 2005
Posts: 430

I keep seeing the word 'Constant-time' performance in several questions but what does it actually mean? To give some context, here is a sample question where it is used:

Which collection class offers contant-time performance for basic operations - add(), remove(), contains() and size()

- TreeSet
- HashSet
- BitSet
- None of the above.

I dont know the answer to the question because i dont know what constant-time performance means..
Stephan van Hulst

Joined: Sep 20, 2010
Posts: 4094

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.
Sebanti Sanyal
Ranch Hand

Joined: Nov 07, 2011
Posts: 58

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.
Dan Drillich
Ranch Hand

Joined: Jul 09, 2001
Posts: 1183
An interesting discussion about HashSet performance.


William Butler Yeats: All life is a preparation for something that probably will never happen. Unless you make it happen.
I agree. Here's the link:
subject: What does constant-time performance mean.
jQuery in Action, 3rd edition