permaculture playing cards*
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
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "What does constant-time performance mean. " Watch "What does constant-time performance mean. " New topic
Author

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
Bartender

Joined: Sep 20, 2010
Posts: 3594
    
  14

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.
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: 1167
An interesting discussion about HashSet performance.

Regards,
Dan


William Butler Yeats: All life is a preparation for something that probably will never happen. Unless you make it happen.
 
Consider Paul's rocket mass heater.
 
subject: What does constant-time performance mean.
 
Similar Threads
How to get Client's Mac Address?
assignment problem
compile time constant
Compile Time Constants...
Compile time !!