CODEWITHSUNDEEP
c++time-complexitybig-ostdvector
Shadab Faizal
Shadab Faizal

Reputation: 5

How to check whether two std::vectors are equal in less than O(n) time complexity

We can compare two vector using for loop like this

    bool checkEquality(vector<int> &A, vector<int> &B){
         if(A.size() != B.size())
             return false;
         int i=0,j=0;
         while(i<A.size() && j<B.size()){
             if(A[i++] != B[j++])
                 return false;
         return true;
    }

but this take O(n) time if elements in vector is n I want to know is there any better way to check whether two vectors are equal or not

and plus what is the time complexity for this code snippet

if(A==B) 
   return true;
else 
   return false;

is the above code works faster than O(n)

Upvotes: 0

Views: 404

Answers (1)

John Zwinck
John Zwinck

Reputation: 249462

is there any better way to check whether two vectors are equal

Yes there is: A == B works fine, and is much simpler than your code.

is A == B faster than O(n)

No, that would be impossible in the general case. We can only do better than O(n) if we know something about the data, such as that differences are always found near the beginning or the end.

Upvotes: 2

Related Questions