What is meant by constant time?

Question

I am studying about algorithm, but I don't get about constant time algorithm.

What that mean and How different with Linear Time Algorithms.

Thanks,

Answer 1

Constant time simply means that regardless of the size of the input to a function, the cost always remains the same.

Here is a simple example, imagine you have a function called deleteHead, which when given a node in a linked list, returns the next one:

function deleteHead(list) {
   if(list == null)
      return null;
   return list.next;
}

Regardless of the size of the list you give this function (ten items, or a billion of them), it always does only a single thing making it a constant time algorithm O(1).

A linear algorithm by comparison, would have to examine all N elements of the linked list to perform some computation, meaning that processing a larger list takes more time. Classically, adding an element to the end of a linked list is linear time, if you don't maintain an end pointer.

Answer 2

This is found in most basic computer science books.

It simply describes the dependency between the input length of an algorithm or size of an object (depending on the application) and the time an operation takes. E.G. using a list it requires a constant amount of steps to add an object at the front/back, no matter how large the list is.

Linear time is required to find a specific item in a list (in the worst and average case)- if you have a list twice as long, you will have to look at twice as many items to find the one you are looking

Answer 3

When changing the input size for a constant-time algorithm, the runtime won't grow.

For e.g. linear algorithms, when changing the input size, the runtime grows (linearly).

For even worse runtimes, say, exponential, the runtime grows exponentially when changing input size.

For examples, see Wikipedia: Time complexity

Answer 4

For constant time algorithms, the time of execution is independent of the size of the input. For linear time, the execution time increases linearly with the input size.