Big O Algebra simplify
big-o, data-structures, math
Solution
1. We omit all constants
Well, strictly speaking, you don't omit all constants, only the outermost multiplicaive constant. That means `O(cf(n)) = O(f(n))`. Additive constants are fine too, since `f(n) < f(n)+c < 2f(n)` starting with some `n`, therefore `O(f(n)+c) = O(f(n))`.
But you don't omit constants inside composite functions. Might be done sometimes (`O(log(cn))` or even `O(log(n^c))` for instance), but not in general. Consider for example `2^2n`, it might be tempting to drop the 2 and put this in `O(2^n)`, which is wrong.
2. We ignore lower powers of n
True, but remember, you don't always work with polynomial functions. You can generally ignore any added asymptotically lower functions. Say you have `f(n)` and `g(n)`, when `g(n) = O(f(n))`, then `O(f(n) + g(n)) = O(f(n))`.
You cannot do this with multiplication.
Problem
To simplify a big O expression - We omit all constants - We ignore lower powers of n For example: `O(n + 5) = O(n)` `O(n² + 6n + 7) = O(n²)` `O(6n1/3 + n1/2 + 7) = O(n1/2)` Am I right in these examples?