algorithm - クイックソートと二分探索を使った集合差分の複雑さはどれ?

Question

2 つのセット A、B があり、セットの差 A - B を計算したい場合、平均複雑度 O(n * log n) を持つクイックソートで B の最初の要素を並べ替え、バイナリで B の A から各要素を検索した後複雑さO（log n）を持つ検索、説明されたセット差分アルゴリズム全体はどの複雑さを持ちますか？クイックソートとバイナリ検索を使用することを考えると。このアルゴリズムを使用して集合差の複雑さを計算する方法を試してみました: O(n * log n) + O(log n) = O(n * log n + log n) = O(log n * (n + 1)) = O((n + 1) * ログ n)。それが正しいか ？

Answer 1

O (n * log n) + O (log n) = O (n * log n)

http://en.wikipedia.org/wiki/Big_O_notation#Properties

関数が n の多項式によって制限される場合、n は無限大になる傾向があるため、多項式の下位の項は無視できます。