Complexity of absolute difference and sum

  1. |O(f(n)) – O(f(n))| = O(f(n)). That is basically the only thing you can say about it. This is because you’re subtracting, from a function growing at most like f(n), another function growing at most like f(n). The result (pre the absolute value) can be even negative (e.g., when subtracting 2 f(n) = O(f(n)), but it is clearly not larger than a function growing like f(n).

  2. O(f(n)) + O(f(n)) = O(f(n)). This is easy to prove throught the basic definition of O.

Browse More Popular Posts

Leave a Comment