Question

Find and explain an example of some programming processing task that demonstrates one of the common growth rate functions.

For example, the constant time function describes a task in which the work steps are the same regardless of the amount of input.
The linear time function describes a task in which the work steps grow just as much as the input size does ('1 for 1').
The quadratic time function describes a task in which the work steps grow by as much as the square of the input size (e.g. 4 work steps are required it the input size is 2, 9 steps required for 3).

It is important in thinking about this topic to look at a problem or algorithm, decide on the meaningful work steps it does, then look at how much the work steps grow as the input size increases.

Answer 1

The three time functions described above are constant time function, linear time function, quadratic time function. The time complexity is generally measured by the number of elementary operations a program has to perform .The elementary functions will have a prefixed value of time to perform. Let's go through them one by one.

Constant time function:

Constant time function indicates the time to perform a operation is constant i.e O(1). Also it can be noted that only the programs which take O(1) are not called constant but also programs which take fixed amount of time for whatever the input are also called as constant time functions. For example addition of two numbers can be completed in O(1) time and at the same point exchanging of two values i.e swapping of numbers also takes a constant time regardless of the input given.

So we can say if T(n) is O(constant value) which is noted as T(n) is equal to O(1) then it's a constant time function.

Linear time function:

A program is said to be varying in linear time function if it's time complexity is O(n). Also it can vary along with a constant c i.e if the size of input n increases then time complexity may increase by O(cn) which is linear time. The most common example is to add the elements in a list. If the size of the list increases then time to add them also increases linearly. Most of the programs both in software and hardware have to be solved in linear time or nearly linear time for effective functioning. Content addressable memory is an algorithm which runs in linear time. It reads the input and stores them and also check the input with already stored values and returns their address if they are present. This is used in boyer-moore algorithm.

Quadratic time function:

It represents a program whose time complexity changes square of the input size. If the size of input is n then t(n) is equal to O(n²). This occurs when we nest over the multiple iterations over the given input.

Var hasDuplicates= function (array){

for(var i=0;i<array.length;i++){

var element=array[i];

if(array.slice(i+1).indexOf(element)!==-1)

return true;

else

return false;

}

This is a very good example of quadratic time function because we are searching through the array twice. Firstly we are iterating through the array using for and in the if statement we are passing the rest of array to find the element thus it's taking quadratic time.