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?
+3
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)
+10
source to share