Help in understanding properties of big O notation with norms of vectorsIn Fast Exact Multiplication...

Deromediqm

Deromediqm

Answered

2022-07-22

Help in understanding properties of big O notation with norms of vectors
In Fast Exact Multiplication by the Hessian equation 1,
O ( Δ w 2 ) gets taken from RHS to LHS and Δ w is substituted as rv where r is small scalar and v is a vector. I understand that O ( r v 2 ) = O ( r 2 v 2 ). 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 v 2 disappear form O. Is it because as r is tiny it will govern the O term and v 2 won't matter?

Answer & Explanation

Hassan Watkins

Hassan Watkins

Expert

2022-07-23Added 18 answers

O ( f ( x ) ) 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 g ( x ) O ( f ( x ) ) means that there's some constant C such that for all sufficiently large (or sufficiently small, depending on the direction of the limit) x, | g ( x ) | < C | f ( x ) | . But this means in particular that O() is 'sign-agnostic'; if g ( x ) O ( f ( x ) ), then c g ( x ) O ( f ( x ) ) for all constants c, positive or negative. This same fact is also what 'removes' the dependency on v 2 ; because the limit that's implicit in O() is being taken with respect to r and v doesn't depend on r, the quantity v 2 is 'constant' and can be absorbed into the constant in O().
Hayley Bernard

Hayley Bernard

Expert

2022-07-24Added 5 answers

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 | x | C z for some number C. If we have x = y + O ( z ), 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 | z | C z. So we can say
y = x + O ( z )
too, since y x = z , and | z | = | z | C z. 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.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?