title: Prove or disprove statements about running times
body: <p>I'm working through chapter 3 of CLRS, which is about running times and would like to work through some examples. Since I'm not enrolled in an algorithms class I need to resort to the www for help.</p>
  
  <p>1) n^2 = Big-Omega(n^3)</p>
  
  <blockquote>
    <p>I think this statement is false: if the best case running time is n^3, then the algorithm cannot be n^2, . Even the best case is slower than that.</p>
  </blockquote>
  
  <p>2) n + log n = Big-Theta (n)</p>
  
  <blockquote>
    <p>I think this statement is true, we can ignore the lower term of log n. This gives us a worst-case running time of Big-Oh (n). And a best case running time of Big-Omega (n). I'm not quite sure of this though. Some more clarification would be appreciated.</p>
  </blockquote>
  
  <p>3) n^2 log n =Big-Oh (n^2)</p>
  
  <blockquote>
    <p>I think this.statement is false: the worst case running time should be n^2 log n.</p>
  </blockquote>
  
  <p>4) n log n = Big-Oh (n sqrt (n))</p>
  
  <blockquote>
    <p>Could be true since n log n &lt; n sqrt (n). Not quite sure though.</p>
  </blockquote>
  
  <p>5) n^2 - 3n - 18 = Big-Theta (n^2)
  Really no idea...</p>
  
  <p>6) If f (n) = O (g (n)) and g (n)  = O (h (n)), then f (n) = O (h (n)).</p>
  
  <blockquote>
    <p>Holds by the transitive property.</p>
  </blockquote>
  
  <p>I hope someone Could elaborate a bit on my quite.possibly wrong answers :)</p>