engineering recuitment NIC NIELIT Scientist B 2023 Mock Test Algorithms Searching, Sorting and Hashing Sorting
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting (𝑛 ≥ 2) numbers? In the recurrence equations given in the options below, 𝑐 is a constant.
1
T(𝑛) = 2 T(𝑛/2) + 𝑐n
2
T(𝑛) = T(𝑛 – 1) + T(1) + 𝑐n
3
T(𝑛) = 2T(𝑛 – 1) + 𝑐n
4
T(𝑛) = T(𝑛/2) + 𝑐n