What is the time complexity to find the value of a property of a field that is an object

Question

Instead of:

{
   A: [user_id_1, user_id_2, etc.]
}

I want to create this schema:

{
   A: {
    user_id_1: true,
    user_id_2: true,
    etc...
  }
}

The reason is because in order to find if user_id_x is $in A, if it is an array, the time complexity is O(N).

However, as I understand it, the time complexity to find a key value pair is either O(1) or O(logN).

If I choose the schema design for MongoDB, will it have the performance improvements described abolve?

Answer 1

Yes, if you choose the schema design where the property of the field is an object, the time complexity to find a specific user_id would be O(1) or O(logN), as you mentioned. This is because MongoDB uses a hash table data structure to store objects, which allows for constant time lookups using the key-value pairs. This is a significant improvement over the O(N) time complexity of searching through an array. However, this performance improvement will only be seen if the number of keys is relatively small.