"Q=Q can be used instead of Theta."
"Case I : Quick Sort takes Q(N^2) in case of already sorted input. This is true."
"But does Quick Sort always take first element as pivot?"
It is not mentioned anywhere in the question that Quick sort takes first / last element as PIVOT.
Q(N^2) is only possible if Pivot is First or last element , at the same time array is sorted, with recurrence relation of time complexity T(n) as follows-
T(n)= O(1) [Pivot selection time] + O(N)[Division/Partition Time] + (T(n-1)+T(1)) [Conquer/Recursive call Time] + O(1) [Combine time]
= Q (n^2)
But if I take a randomized Pivot Element for the quick sort which is anyhow not the first or last element of the sorted array , then the recurrence equation of the “Conquer or Recursive Call” part may change to T(n)=T(n/2)+T(n/8) or may be in T(n)=T(n/5)+T(4n/5) which leads in to time complexity Q (N.logN) of that part.
So time Complexity depends on selection of the Pivot element even if the array is sorted.
"Case II : This is false. If no swap happens then bubble sort can stop in single loop. Q(N) is best case. This is false ! "
"But bubble sort needs modification to ensure that."
"Modified bubble sort would take theta(n) time in best case."
If we modify our coding so that if the last two passes have the same result with no change, then only it’s Q(n), otherwise Q(N^2). Why?
Because Bubble sort time complexity depends on two things No of comparisons made and also No of swaps occur. If the array is sorted but not a modified bubble sort is done then even if the no of swaps is Q(1) but still the number of comparisons in 1st pass is (n-1), in second pass is (n-2) and in 3rd pass is (n-3) and so on.... till last pass which results in to Q(N^2) time complexity of bubble sort, if it is not modified.
If it is modified Time complexity is of linear time Q(n) !!
Last two cases are pretty straight Forward i think no confusion everyone can easily judge it .....
"Case III : Merge Sort never takes more than Q(N.logN). This is false."
and
"Case IV : Insertion Sort will finish in Q(N) time in case of sorted input. This is true."
So the question leads to an Ambiguous Tagged one.