Please answer these doubts related to Quiz on Vectors STL

#1
  1. 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);
}

Choose the correct option :
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.

I think it should be O(n) but correct ans is O(n^2).

  1. Given an array of N integers.
    We wish to sort these integers but we must remember what their orignal indices were before sorting.

Choose the correct option :
We cannot achieve this with the inbuilt sort function.
We may build a vector> data where data[i].first = AR[i] and data[i].second = i and sort this vector using sort(data.begin(), data.end()).
We may build a vector> data where data[i].first = i and data[i].second = AR[i] and sort this vector using sort(data.begin(), data.end()).
This cannot be achieved without a custom comparator and two arrays.

Correct option is 2 but option 3 is also same so it can also be correct?

  1. class myStack
    {
    vector < int > stack;
    public:
    int top();
    void pop();
    void push(int x);
    }
    Imagine the vector as a stack. The element at last position of the vector will be treated as top of the stack and element at stack[0] will be treated as the bottom of the stack.

Choose the correct option :

top() and pop() can be implemented to work in O(1) time complexity.

top() and push() can be implemented to work in O(1) time complexity.

either pop() or push() will work in O(N) and the other will work in O(1).

All functions can be implemented to work in O(1) time complexity.

#2

Hey @sahilkhan2312000131

Assumming vector is defined as vector< int > v
its time complexity will be O(n^2).
because total n calls wiil be there and on every call vector get copied to new vector which is O(n) for each call . therefore O(n^2) for n calls
Its not passed by reference but by copy
so for each recursive call a copy of vector is made
So rec reln in terms of time complexity is T(n)=T(n-1) + O(n) ==>T(n-2)+2*O(n) ==> T(1)+n*O(n)==O(n^2)

In 3rd option it will sort according to indices which is same array as before

ITS ANSWER Should be Option D

#3

In 2nd question how are we able to make a vector with each element having first and second element??
In 3rd question, I think push function would take O(n) time once the vector becomes full??

#4

Using user define datatype or by using predefined pair class

pair<int,int> p;
cin>>p.first>>p.second;
make vector of pairs and do that

When vector becomes full it doubles its capacity and while doubling its O(n) but since doubling happens once in a while its not considered in total complexity ,so effective complexity to push is O(1) only

#5

So in second question, it is upon us if we sort using first element or second element. So 3rd option can also be correct.

#6

this will sort acc to first element only

We have to make our own compare function and pass it if want to sort acc to 2nd number
If u don’t know about it then u will learn about it later in the course

#7

Actually I used to think if we have not passed our comparator function with sort then it would not be able to sort pair data type i.e. we anyway have to pass a comparator to sort it so we can use first and even second element for sorting.
But now I got it that even without passing comparator it will sort the vector based on 1st element.

1 Like
#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.