CODEWITHSUNDEEP
c++
Zongyang
Zongyang

Reputation: 35

What is the time complexity of judging if two vectors are equal in C++?

Does it have to compare every element one by one?
In such case it must be O(n) right?

Upvotes: 0

Views: 2934

Answers (2)

Dongwei Wang
Dongwei Wang

Reputation: 495

when you want to compare two vectors.

  • They must be the same type, such as both of them are vector, it is not acceptable to compare two different type vectors, such as the comparison between vector and vector
  • The rules to compare two vectors follow the comparison between two strings, not necessarily to compare all elements.

Generally, in our program, the size of two vectors should already be given (not a variable as the input size), in that situation, the comparison between two vectors is O(1) since it must finish the comparison in a fixed time.

Upvotes: -1

Jerry Coffin
Jerry Coffin

Reputation: 490438

It doesn't necessarily compare all the elements.

If the two vectors are of different lengths, it can return false based only on the difference in length, in constant time.

Otherwise, yes, it has to compare elements until it encounters a difference (all the elements if the two are equal).

Upvotes: 4

Related Questions