The Gateway to Computer Science Excellence

+2 votes

Let us a consider a series of events where a random partition procedure always picks the median element among n distinct numbers dividing the array into two equal halves ( ignore floor and ceiling). What is the probability that such a partition procedure always picks the median element in all subsequent arrays till the entire array is sorted.

+2 votes

The probability of selecting the median among n numbers is 1/n

The probability of selecting the median from the 2 n/2 partitions is (2/n)*(2/n) = 2^{2}/n^{2}

In a similar way the series will appear as (1/n) x (2^{2}/n^{2}) x (4^{4}/n^{4 })x....x (Log n^{log n}/n^{log n-1})

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,382 answers

198,530 comments

105,323 users