Computing the note O-O, O (n) * O (log n) = O (n log n)

I need to develop an algorithm that can do some computation in a given O-notation. It's been a while since I last calculated using O notation, and I'm a little confused about how to add different O records 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 they correct? What other rules have I missed?


source to share

1 answer

The rule for multiplication is really simple:

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


The sum of two O

terms is more difficult 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 the original name is not specified;

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




All Articles