Analysis of algorit

Question

Which of the following statements is/are valid?
1. Time Complexity of QuickSort is Θ(n^2)
2. Time Complexity of QuickSort is O(n^2)
3. For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).
4. Time complexity of all computer algorithms can be written as Ω(1)

Answer 1

Answer : Option 2,3,4 are valid.

Option 1 and 2 : Time complexity of QS as we know is $\Theta (n^2)$ in Worst Case and $\Theta (nlogn)$ in Best or Average case. 

So, We can say that Time complexity of QS is $O(n^2)$ as it will include all the three cases, But We can't say that the Time comp of QS is $\Theta(n^2)$ because then it would mean that QS in all the cases takes  $\Theta(n^2)$ time.

Option 3 : Statement 3 is Itself the definition of $\Theta$ notation.

Option 4 : Whatever computer algorithm you take (even as simple as printing Hello Word), It will definitely take some time... some positive amount of time. Hence, We can say that Every computation algorithm takes $\Omega(1)$ time.. Because $\Omega(1)$ covers all the time complexities possible whether it is Polynomial or Exponential etc.

Answer 2

1. Time Complexity of QuickSort is Θ(n^2) 

1st one is false because Quick sort worst case time complexity is O(n^2) while average and best time complexity is O(nlogn) so we can't derive Θ notation for this.

2. Time Complexity of QuickSort is O(n^2) 

2nd one is true because Quick sort worst case time complexity is O(n^2) and we can also write nlogn=O(n^2)

3. For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). 

3rd one is right because for finding Θ notation we are finding tightest upper bound and tightest lower bound which is nothing but Big-Oh and Big-Omega

4. Time complexity of all computer algorithms can be written as Ω(1)

4th one is true because it said at least algorithm will take constant time i.e it may be constant or it may be n^2 or it may be 2^n but algorithm will take time constant time or more then that.