Which of the following statements is/are true?
1
Recurrence relation for number of comparisons in binary search is T(n) = T(n/2) + 2
2
Recurrence relation of merge sort in worst case is T(n) = 2T(n/2) + Θ(n)
3
Recurrence of quicksort in worst case is T(n) = 2T(n/2) + O(1)
4
3-way merge sort is T(n) = 3T(n/3) + O(n)