A student just learned about vectors. Now he wants to implement a class vector which can support dynamic array of integers.
He writes the following code :
class myVector
{
int * data; // pointer to underlying array to store elements
int capacity; //size of the underlying array
int elementsInVec; //number of elements currently in the vector
public:
myVector(){
data = new int[1000];
elementsInVec = 0, capacity = 1000;
}
void push_back(int x)
{
if( elementsInVec == capacity)
{
int * temp = new int[capacity + 1];
for(int i = 0; i < capacity; i++)
temp[i] = data[i];
temp[capacity++] = x;
delete data;
data = temp;
}
else data[elementsInVec] = x;
elementsInVec++;
}
// more code
}
What is the time complexity of push_back as implemented by the student? Let N be the current size of the vector.