title: Asymptotic Notation
body: <p>This is a problem on <strong>Asymptotic Notation</strong> from the assignment of MIT OpenCourse <em>Introduction to Algorithm</em>:<br>
  For each of the following statements, decide whether it is <strong>always true</strong>, <strong>never true</strong>, or <strong>sometimes true</strong> for asymptotically nonnegative functions <em>f</em> and <em>g</em>. If it is <strong>always true</strong> or <strong>never true</strong>, explain why. If it is <strong>sometimes true</strong>, give one example for which it is true, and one for which it is false.</p>
  
  <pre><code>f(n) ≠ O(g(n)) and g(n) ≠ O(f(n))   (both are Big-O notes)
  </code></pre>
  
  <p>I think it is <strong>never true</strong>. Here's my proof:</p>
  
  <pre><code>   f(n) ≠ O(g(n))
  =&gt; f(n) = w(g(n))   (little-omega note)
  =&gt; g(n) = o(f(n))   (little-o note)
  =&gt; g(n) = O(f(n))   (big-O note)
  </code></pre>
  
  <p>the result contradicts to <code>g(n) ≠ O(f(n)) (Big-O note)</code>. Likewise, </p>
  
  <pre><code>   g(n) ≠ O(f(n))
  =&gt; g(n) = w(f(n))   (little-omega note)
  =&gt; f(n) = o(g(n))   (little-o note)
  =&gt; f(n) = O(g(n))   (big-O note)
  </code></pre>
  
  <p>which contradicts to <code>f(n) ≠ O(g(n)) (Big-O note)</code>.</p>
  
  <p>The solution says it is <strong>sometimes true</strong>:</p>
  
  <pre><code>For f(n) = 1 and g(n) = ||n*sin(n)|| it is true,  
  while for any f(n) = O(g(n)), e.g. f(n) = g(n) = 1, it is not true.
  </code></pre>
  
  <p>Where have I done wrong in my proof? Also, I cannot understand the solution. <code>||n*sin(n)||</code> looks like <strong>vector norm</strong> to me.</p>