Help in understanding properties of big O notation with norms of vectorsIn Fast Exact Multiplication...
Help in understanding properties of big O notation with norms of vectors
In Fast Exact Multiplication by the Hessian equation 1,
gets taken from RHS to LHS and is substituted as rv where r is small scalar and v is a vector. I understand that . But what I don't get is how did the sign of O not become negative when it was taken to LHS. And why did disappear form O. Is it because as r is tiny it will govern the O term and won't matter?
Answer & Explanation
refers to a quantity that's bounded (in the limit) by some multiple of f(x); it properly (IMHO) represents a set. That is, to say that means that there's some constant C such that for all sufficiently large (or sufficiently small, depending on the direction of the limit) x, . But this means in particular that O() is 'sign-agnostic'; if , then for all constants c, positive or negative. This same fact is also what 'removes' the dependency on ; because the limit that's implicit in O() is being taken with respect to r and v doesn't depend on r, the quantity is 'constant' and can be absorbed into the constant in O().
When we write x=O(z), where x is some expression, and z is some other quantity, then we mean that x is a quantity such that for some number C. If we have , then we really mean x−y=O(z) in the sense I just described. So x−y is equal to some quantity z′ such that . So we can say
too, since , and . So the minus sign does not need to be kept track of, and it's best to think of O(z) as meaning a quantity, whose absolute value is bounded by a constant times z.