how is the complexity n^2 . Shoudn’t it be n?
Doubt in question 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) ? O(N) O(1) O(M) O(N + M)
Here it is written that it takes constant time -> http://www.cplusplus.com/reference/vector/vector/swap/.
It might be just changing names of the vector.
lets say
v1 = {1,2,3,4};
v2 = {1,2};
after swapping =>
v2 = {1,2,3,4}
v1 = {1,2}
so v1 and v2 now points to different vector, without accessing the elements of the vector.
sry by mistake i copied the wrong question
Q3. 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); } 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.
@Akshita99
here we are passing vector as value so on every call new vector is created and all values get copied from original vector to newly created vector . this process takes O(n) time becuase to copy all elements we need to iterate complete vector of size N.
and because total n calls will be there ,overall complexity will be O(n^2)
ok thank you. One more doubt was there
Which of the following can be used to store a simple undirected graph with N nodes? vector < int > graph [ N + 1 ] bool graph [ N + 1 ][ N + 1 ] vector < vector < int > > graph(N+1) All of them.
i think someone else is taking that
sorry i didn’t get you
@Akshita99
answer is all of them
a) first one is array of vector
b) second one is adjancecy matrix
c) third one is vector of vector
we can store graph in all of them (u should know basic graph theory to answer this question)