CODEWITHSUNDEEP
algorithmbig-o
Androme
Androme

Reputation: 2449

Big-O notation calculation, O(n) * O(log n) = O(n log n)

I need to design an algorithm that is able to do some calculations in given O notation. It has been some time since I last calculated with O notation and I am a bit confused on how to add different O notations together. 

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

O(n) + O(n) = O(2n) = O(n)

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

Are these correct? What other rules have I overlooked?

Upvotes: 3

Views: 1969

Answers (1)

phihag
phihag

Reputation: 287865

The rule for multiplication is really simple:

O(f) * O(g) = O(f * g)

The sum of two O terms is harder to calculate if you want it to work for arbitrary functions.
However, if f ∈ O(g), then f + g ∈ O(g).

Therefore, your calculations are correct, but your original title is not;

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

Upvotes: 11

Related Questions