GATE CSE
First time here? Checkout the FAQ!
x
0 votes
37 views

asked in Algorithms by (275 points)   | 37 views

1 Answer

+2 votes

Choose the median in constant time, because the algorithm is implemented as an array and you can find the median in constant time.

Then, split the array with respect to the median.

The recurrence relation will be:

T(n) = 2T($\frac{n}{2}$) + 1

(1 because we are doing a constant work and then splitting the array)

Solve by master's theorem, you will get $\Theta (n)$

NOTE: If the data structure used was a linked list or if the elements were not in ascending order, the complexity would have been $\Theta (nlogn)$

answered by Boss (8.1k points)  
edited by


Top Users Aug 2017
  1. ABKUNDAN

    4660 Points

  2. Bikram

    4366 Points

  3. akash.dinkar12

    3258 Points

  4. rahul sharma 5

    3042 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2410 Points

  7. just_bhavana

    2100 Points

  8. Tesla!

    1918 Points

  9. stblue

    1682 Points

  10. joshi_nitish

    1608 Points


24,928 questions
32,024 answers
74,385 comments
30,113 users