posted 5 years ago

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:

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

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

Saloon Keeper

Posts: 6980

110

posted 5 years ago

- 2

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.

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.*

posted 5 years ago

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.

It is sorta covered in the JavaRanch Style Guide. |