Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

What does constant-time performance mean.

 
O. Ziggy
Ranch Hand
Posts: 430
Android Debian VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 5912
65
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 58
C++ Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1183
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
An interesting discussion about HashSet performance.

Regards,
Dan
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic