title: Algorithms complexity
body: <p>i need some help with algorithms complexity, i should be able to answer questions like these:</p>
  
  <ol>
  <li><p>Let f(n) and g(n) denote the message complexity of the Chang &amp; Roberts algorithm in the best and in the average case, respectively.
  Which of the following asymptotic relations is wrong?</p>
  
  <p>a) f(n) = Θ(g(n))<br>
  b) f(n) = O(g(n))<br>
  c) f(n) = o(g(n))<br>
  d) g(n) = Ω(g(n))</p></li>
  <li><p>Let f(n) and g(n) denote the message complexity of the Chang &amp; Roberts algorithm in the worst and in the average case, respectively. Which of the following asymptotic relations is wrong?</p>
  
  <p>a) f(n) = Θ(g(n))<br>
  b) f(n) = Ω(g(n))<br>
  c) f(n) = !(g(n))<br>
  d) f(n) = O(g(n))</p></li>
  </ol>
  
  <p>I know that complexities for Chang &amp; Roberts algorithm are:</p>
  
  <p>Θ(n^2)      worst case</p>
  
  <p>Θ(n)        best case</p>
  
  <p>Θ(n log n)  average case</p>
  
  <p>The answer to question 1 is a, for question 2 are a,d.
  I know the differences (definitions) between Θ, O e Ω but i'm not able to apply them to these questions. Can you help me?</p>
  
  <p>For example, in the 1st question, is it correct to see answers in this way?</p>
  
  <pre><code>f(n) = Θ(n), g(n) = Θ(n log n)
  
  a) Θ(n) = Θ(Θ(n log n)) 
  b) Θ(n) = O(Θ(n log n)) 
  c) Θ(n) = o(Θ(n log n)) 
  d) g(n) = Ω(Θ(n log n))
  </code></pre>