Big O Notation, when can we drop constants legally?
big-o, complexity-theory
Solution
At this point, it starts to be a good idea to go back and look at the formal definition for big O notation. Essentially, when we say that `f(x) is O(g(x))` we mean that there exists a constant factor `a` and a starting input `n0` such that for all `x >= n0` then `f(x) <= a*g(x)`.
For a concrete example, to prove that `3*x^2 + 17` is `O(n^2)` we can use `a = 20` and `n0 = 1`.
From this definition it becomes easy to see why the constant factors get dropped off - its just a matter of adjusting the `a` to compensate. As for your `1/log(n)` question, if we have `f(x) is O(g(x))` and `g(x) is O(h(x))` then we also have `f(x) is O(h(x))`. So yes, `10*n^3/log(n) + x is O(n^3)` but that is not a tighter upper bound and it is a weaker statement than saying that `10*n^3/log(n) + x is O(n^3/log(n))`. For a tight bounds you would want to use big-Theta notation instead.
Problem
I know in Big O Notation we only consider the highest order, leading polynomial term because we are basically placing this theoretic worst case bound on compute-time complexity but sometimes I get confused on when we can legally drop/consider terms as constants. For example if our equation ran in O((n^3)/3) --> we pull out the "1/3" fraction, treat it as a constant, drop it, then say our algo runs in O(n^3) time. What about in the case of O((n^3)/((log(n))^2))? In this case could we pull out the 1/((log(n)^2)) term, treat it as a constant, drop it, and then ultimately conclude our algorithm is O(n^3). It does not look like we can, but what differentiates this case from the above case? both can be treated as constants because their values are relatively small in comparison to the leading polynomial term in the numerator but in the second case, the denominator term really brings down the worst case bound (convergence) as n values get larger and larger.