Regarding doubts in the quiz

#1

doubts in question 3 6 7 8 9 in the 2nd quiz on stl . Please help

#2

@imsharan0105 what is your doubt please explain?
If you want the correct answers you can see them there only

#3

I am having doubts in each of the questions . Please explaine to me the logic behind the right answer

#4

@imsharan0105

Vector STL#3
Predict the time complexity of the following recursive function, given the vector is of size N and the initial call is calSum(v, 0).

int sum = 0;
void calcSum(vector v, int i)
{
    if(i == v.size())
        return;
    sum += v[i];
    calcSum(v, i+1);
}

Choices
O(N)
O(N^2)
Depends upon the compiler, but O(N) in most cases.
Depends upon the compiler, but O(N^2) in most cases.

In this, the vector is passed by reference, so for each call the whole vector is called in O(n) time thus making the time complexity O(n * n)

#5

@imsharan0105

Vector STL#6
Given two vectors v1 and v2, we can swap the contents of the two vectors manually using a O(N + M) time algorithm where N = v1.size() and M = v2.size().

However the vector class provides an inbuilt function swap().

What is the time complexity of v1.swap(v2) ?

Choices
O(N)
O(1)
O(M)
O(N + M)

complexity: constant -> O(1)
source: http://www.cplusplus.com/reference/vector/vector/swap/

#6

@imsharan0105 I dont understand what is the doubt in q7? All the approaches have been explained.

STL#8
What is the time complexity of push_back as implemented by the student? Let N be the current size of the vector.

Choices
O(1) on average
O(N) per call to push_back().
O(1) for the 1st 1000 calls to push_back and O(N) for every call after that.
O(logN) on average.

In the constructor, capacity was made 1000. So for the first 1000 calls, push_back can be done easily. But for any call after that, capacity is not enough, so a new vector has to be made with sufficient capacity and all the data from the previous vector will be copied in O(n) time

Q9, are you familiar with graphs?