C++ constant time ,linear time and logarithmic time


in C++ local time ,constant time and linear time are some of the terms use to classify the operations that depends on some certain factors.They are mainly use when dealing with STL containers and the operations performed on there elements.

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

Constant time

Suppose if the elements in the containers are presented in such a way that performing 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 push_back function if the object has pre-allocated space the addition of elements is done in constant time.Well if the vector has pre-allocated space,to add new elements the number of elements currently held by the container is not a necessary factor to take into account,we can directly append the element and so the operation is done in constant time.But if the vector has no pre-allocated 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 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

LinK:vector::push_back


 


Stop wasting time,earn money($$$) from your website-Join Now!


Linear time

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

examples of linear time operations

The best example of operations having linear time is the resize() function of sequence containers.This is due to the fact that to to reach the last elements of the sequence you have to go through the whole elements one by one.So obviously it depends on the number of elements in the sequence.

Link:vector::resize function

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

vec.resize( 5);

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

Output

2
323
8
0
0






Logarithmic time

If the sequence of the containers is arrange in such a way that it allows insertions,removal or lookups of the elements is dependent on the logarithms 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 the data in the sequence usually is of logarithmic time find() and operator[] function is map container to name a few.

Link:map::operator[] function

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.


 


Stop wasting time,earn money($$$) from your website-Join Now!