Question

C++

Analyze the following function in terms of the number of equality ( == ) comparisons and the number of push_back operations, assuming that both vectors have the same size n. // Returns vector containing everything from a that is // also in b. vector int> set_int(vector<int>& a, vector int>& b) { vector int> out; for(int x : a) for(int y : b) if(x -- y) { out.push_back(x); break; > return out; What kind of inputs results in the best-case performance? What kind results in the worst?

Answer 1

Ans

Best Case :- When both a and b vectors are empty

Worst Case :- When both vectors have same elements i.e elements in vector a present in vector b (order of elements doesn't matter).

Analysis

there is nested for loop that

runs for each element of vector a

and for each element of a it compares with each element of b

if both found to be same then element is push in vector out

Numberof equality comparison = (size of vector)²

0 <= Number of push operation <= size of vector

If any doubt ask in the comments