Help in understanding properties of big O notation with norms of vectorsIn 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?

Question

Help in understanding properties of big O notation with norms of vectorsIn 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&#039;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&#039;t matter?

Hassan Watkins · Accepted Answer

O  (  f  (  x  )  )  refers to a quantity that&#039;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&#039;s some constant C such that for all sufficiently large (or sufficiently small, depending on the direction of the limit) x,       |    g  (  x  )      |    &amp;lt;  C      |    f  (  x  )      |  . But this means in particular that O() is &#039;sign-agnostic&#039;; 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 &#039;removes&#039; the dependency on             ‖      v      ‖        2  ; because the limit that&#039;s implicit in O() is being taken with respect to r and v doesn&#039;t depend on r, the quantity             ‖      v      ‖        2   is &#039;constant&#039; and can be absorbed into the constant in O().

Hayley Bernard · Accepted Answer

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&#039;s best to think of O(z) as meaning a quantity, whose absolute value is bounded by a constant times z.

Answered question

Answer & Explanation

New Questions in Precalculus