Time Complexity of $addToset vs $push when element does not exist in the Array

Question

Given: Connection is Safe=True so Update's return will contain update information. Say I have a documents that look like: ``` [{'a': [1]}, {'a': [2]}, {'a': [1,2]}] ``` And I issue: ``` coll.update({}, {'$addToSet': {'a':1}}, multi=True) ``` The result would be: ``` {u'connectionId': 28, u'err': None, u'n': 3, u'ok': 1.0, u'updatedExisting': True } ``` Even when come documents already have that value. To avoid this I could issue a command. ``` coll.update({'a': {'$ne': 1}}, {'$push': {'a':1}}, multi=True) ``` What's the Time Complexity Comparison for $addToSet vs. $push with a $ne check ?

Accepted Answer

Looks like $addToSet is doing the same thing as your command: $push with a $ne check. Both would be O(N)

https://github.com/mongodb/mongo/blob/master/src/mongo/db/ops/update_internal.cpp

if speed is really important then why not use a hash:

instead of:

```
{'$addToSet': {'a':1}}
{'$addToSet': {'a':10}}
```

use:

```
{$set: {'a.1': 1}
{$set: {'a.10': 1}
```

Time Complexity of $addToset vs $push when element does not exist in the Array

Solution

Problem