C++ constant time ,linear time and logarithmic time

Here we will discuss some of the terms like C++ constant time, C++ linear time and C++ logarithmic time. In C++, these are terms used to classify operations that depend on some certain factors. They are mainly used when dealing with STL containers and the operations performed on it’s elements.

i)constant time
ii)linear time
iii)logarithmic time


C++ Constant time

Suppose, if the elements in the container are present in such a way that operations like insertions, copying and removal of elements from and to the containers does not depend on the number of elements in the container. Then such operations will be considered as operations performed in constant time.

examples of constant time operations

In a vector STL container when using the push_back function, if the object has pre-allocated some space the addition of elements is done in constant time. Since the vector has pre-allocated some space, to add new elements the number of elements currently held by the container is not a factor that must be taken into account. We can directly append the element and so such operation is done in constant time.

But if the vector has not pre-allocated any space, the container has to reallocate new space that can suitably fit the currently held elements and the incoming elements, here searching for the required storage does depend on the number of elements and certain other factors. In this case, the push_back call is not performed in constant time.

vector<int> vec1 {2,3} ,
vec2 ;

vec2.reserve( 3 ); //pre-allcoate space

vec2.push_back(3); //done in constant time/span>

vec1.push_back(34) ; //not done in constant time


C++ linear time

If the number of operations to be performed depends on the number of elements of the sequence or containers then the operations is said to be done in linear time.

examples of linear time operations

The best example of operation performed in linear time is the operation peformed by the resize() function of a container. The function resize the storage of a container and so to reach the last element it has to go through each of the element one by one. Hence, it depends on the number of elements in the sequence.

vector<int> vec{2 ,323 ,8};

vec.resize( 5);

for(auto elem:vec)
{
cout<< elem << endl;
}

Output

2
323
8
0
0


C++ Logarithmic time

If the sequence of the container is arrange in such a way that it allows insertions, removal or lookups of the element is dependent on the logarithm of the number of elements of the sequence. Such operation is said to have logarithmic time.

Example of logarithmic time operation

The operations that require searching of a data in the sequence usually is of logarithmic time, functions such as find() and operator[] of a map container are of this type.

 map<int,char> mp{{45 ,’4′} ,{ 90 , ‘5’} , { 900 , ‘%’} , { 12 ,’2′} , { 500 , ‘9’} , {67 , ‘*’ } };

cout<< mp[12] ; //logarithmic time

Output : 2


Side note

Constant time operation is faster than linear time and logarithmic time operation. The reason is obviously due to non-dependent of operations on other factors like number of elements and logarithms use.




Leave a Reply

Your email address will not be published. Required fields are marked *