While I understand the concept of both complexity of algorithms and logarithmic complexity in programming, I do not know how to determine the complexity of a logarithm that includes variables of different powers.
Here are some examples:
log(x^2 + 3x^3) = O(?)
log(x^3 + 5) = O(?)
Any help would be very appreciated.
Thank you.
O(log(x))
Just because of the mathematical rule that log(xk) = k⋅log(x) (that's strictly from the definition of log)
Also, we know that O is an asymptotic multiplicative notation, so multiplying by a constant does not affect it.
Proof:
log(x² + 3x³) ≤ log(4x³) ≤ log(x⁴) for big enough x
So log(x²+3x³) ≤ log(4x³) ≤ log(x⁴) = 4⋅log(x) which we know is O(log(x)) by definition
This is proof of the upper O bound
On the other direction (Showing Theta which isn't needed but you might be interested in)
log(x²+3x³) ≥ log(x²) >= 2⋅log(x) which is O(log(x)) by definition