Which one of the following is the recurrence equation for the worst case time…

PYQ GATE 2015

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting nn ( ≥ 2) numbers? In the recurrence equations given in the options below, cc is a constant.

  1. A.

    𝑇(𝑛)=2 𝑇(𝑛/2)+𝑐n𝑇(𝑛) = 2 \ 𝑇(𝑛/2) + 𝑐n

  2. B.

    𝑇(𝑛)=𝑇(𝑛−1)+𝑇(1)+𝑐n𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑇(1) + 𝑐n

  3. C.

    𝑇(𝑛)=2𝑇(𝑛−1)+cn 𝑇(𝑛) = 2𝑇(𝑛 − 1) + cn

  4. D.

    𝑇(𝑛)=𝑇(𝑛/2)+𝑐n𝑇(𝑛) = 𝑇(𝑛/2) + 𝑐n

Attempted by 736 students.

Sign up free to check your answer

Sign up free

Explore the full course: Algorithms

Loading lesson…