3

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?

2
  • I have edited the title (formerly O(n) + O(log n) = O(n log n)) to be correct now.
    – ninjagecko
    Mar 14, 2012 at 0:26
  • My comment is tangential, but some may find it interesting. The notation O(log n) occasions more confusion than almost anything I have seen in computer science. Almost everybody seems to believe that O(log n) differs from O(1) -- except that it doesn't. You can prove that it doesn't by application of L'Hospital's rule. One should hesitate to abandon a clean algorithm to improve O(log n) to O(1), even if n == 1 billion. The gains simply aren't there (you can run the numbers if you don't believe me), whereas the gains are indeed there if the abandoned algorithm is, say, O(sqrt(n)).
    – thb
    Mar 17, 2012 at 23:11

1 Answer 1

11

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)
19
  • Thank you, i though so, but got a bit confused when trying to juggle the algorithm :D thank you for your quick response.
    – Androme
    Mar 14, 2012 at 0:17
  • Wouldn't that make it ... incorrect? That is, max(n, log n) => n?
    – user166390
    Mar 14, 2012 at 0:18
  • Yes, the relation in the title of the post is incorrect: O(n) + O(log n) = O(n log n). But the relation he made in the post is correct: O(n) * O(log n) = O(n log n).
    – sch
    Mar 14, 2012 at 0:20
  • @sch Oops, the rules are correct, but the conclusion is not, is what I should have said. It is hardly fair to say "correct" in this case.
    – user166390
    Mar 14, 2012 at 0:22
  • 1
    Why don't you just write "For f = O(g): O(f) + O(g) = O(g)"? Mar 17, 2012 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.