mongoDBでインデックス付きデータを検索することの複雑さ（Big-O）は何ですか？

これは、ほとんどすべてのデータベースと同様にBツリーインデックスであるため、O（log n）ルックアップ時間があります。

正規表現検索は、全表スキャンまたは全索引スキャンを実行する必要があるように聞こえます。どちらもO（n）です。式がプレフィックスアンカーされている場合は、範囲だけをスキャンする必要がありますが、それでもO（n）としてカウントされると思います。