title: Asymptotic Analysis questions
body: <p>I found a couple questions on geeksforgeeks.org that i can't seem to understand(#1 and #3). I was hoping someone could clarify the answers for me:</p>
  
  <p>clarify whether true/valid or false</p>
  
  <p>1.Time Complexity of QuickSort is Θ(n^2) </p>
  
  <p>I answered true but it is false, why?  If quicksort has a time complexity of O(n^2) and we know that Θ(g(n))={f(n) where c1*g(n) &lt;= f(n) &lt;=c2*g(n) and n >= n0} then doesn't that prove that it is true since c2*g(n) being the upper bound can equal f(n)?</p>
  
  <p>2.Time Complexity of QuickSort is O(n^2) - true</p>
  
  <p>3.Time complexity of all computer algorithms can be written as Ω(1)</p>
  
  <p>This is true but i have no understanding of why this is true. A search algorithm can have a lower bound of Ω(1) assuming we find what we were looking for on the first element but how does this hold true for ALL computer algorithms such as insertion sort algorithm where the worst case is O(n^2)?</p>
  
  <p>link:
  <a href="http://www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/" rel="nofollow">http://www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/</a></p>