The Gateway to Computer Science Excellence
+2 votes
298 views
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.
in Algorithms by Junior (835 points) | 298 views

1 Answer

+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) = 22/n2

In a similar way the series will appear as  (1/n) x (22/n2) x (44/n)x....x (Log nlog n/nlog n-1)

So the probability of picking median till the entire array is sorted will be    $\frac{\prod_{i=0}^{log n} (2^{i})^{2^{i}}}{(n^{2})^{\frac{(Log n-1)Log n}{2}}}$

by Active (2.6k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,382 answers
198,530 comments
105,323 users