Revisions to Help with deterministic selection algorithm

Commonmark migration

Source Link

edited Jun 16, 2020 at 10:30

1

All we know what is Deterministic Selection Algorithm:

Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group $S[i]$, with $i$ ranging from $1$ to $n/5$.
Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group $S[i]$, with $i$ ranging from $1$ to $n/5$.
Find the median of each group. (Call this $x[i]$). This takes $6$ comparisons per group, so $6n/5$ total (it is linear time because we are taking medians of very small subsets).
Find the median of each group. (Call this $x[i]$). This takes $6$ comparisons per group, so $6n/5$ total (it is linear time because we are taking medians of very small subsets).
Find the median of the $x[i]$, using a recursive call to the algorithm. If we write a recurrence in which $T(n)$ is the time to run the algorithm on a list of n items, this step takes time $T(n/5)$. Let M be this median of medians.
Find the median of the $x[i]$, using a recursive call to the algorithm. If we write a recurrence in which $T(n)$ is the time to run the algorithm on a list of n items, this step takes time $T(n/5)$. Let M be this median of medians.
Use M to partition the input and call the algorithm recursively on one of the partitions, just like in quickselect.
Use M to partition the input and call the algorithm recursively on one of the partitions, just like in quickselect.

In the case of dividing the array into five groups, we get the recurrence: $T(n)=T(n/5)+T(7n/10)$. That simply means that the value returned by partitioning is al least $3n/10−3/2$ and at most $7n/10+3/2$. However, what happens if we divide the array into 3 groups? What will be the upper and lower bounds? And what will be the recurrence of the runtime of the whole algo?

In the case of dividing the array into five groups, we get the recurrence: $T(n)=T(n/5)+T(7n/10)$. That simply means that the value returned by partitioning is al least $3n/10−3/2$ and at most $7n/10+3/2$. However, what happens if we divide the array into 3 groups? What will be the upper and lower bounds? And what will be the recurrence of the runtime of the whole algo?

My thoughts: So the upper bound for $k=5$ is $7n/10 +3/2$. However, I do not understand where this $3/2$ come from? So for $k=3$ it should be like $2n/3 +?$. And also please explain what will be the lower bound? Thanks in advance.

All we know what is Deterministic Selection Algorithm:

Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group $S[i]$, with $i$ ranging from $1$ to $n/5$.
Find the median of each group. (Call this $x[i]$). This takes $6$ comparisons per group, so $6n/5$ total (it is linear time because we are taking medians of very small subsets).
Find the median of the $x[i]$, using a recursive call to the algorithm. If we write a recurrence in which $T(n)$ is the time to run the algorithm on a list of n items, this step takes time $T(n/5)$. Let M be this median of medians.
Use M to partition the input and call the algorithm recursively on one of the partitions, just like in quickselect.

In the case of dividing the array into five groups, we get the recurrence: $T(n)=T(n/5)+T(7n/10)$. That simply means that the value returned by partitioning is al least $3n/10−3/2$ and at most $7n/10+3/2$. However, what happens if we divide the array into 3 groups? What will be the upper and lower bounds? And what will be the recurrence of the runtime of the whole algo?

My thoughts: So the upper bound for $k=5$ is $7n/10 +3/2$. However, I do not understand where this $3/2$ come from? So for $k=3$ it should be like $2n/3 +?$. And also please explain what will be the lower bound? Thanks in advance.

All we know what is Deterministic Selection Algorithm:

Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group $S[i]$, with $i$ ranging from $1$ to $n/5$.
Find the median of each group. (Call this $x[i]$). This takes $6$ comparisons per group, so $6n/5$ total (it is linear time because we are taking medians of very small subsets).
Find the median of the $x[i]$, using a recursive call to the algorithm. If we write a recurrence in which $T(n)$ is the time to run the algorithm on a list of n items, this step takes time $T(n/5)$. Let M be this median of medians.
Use M to partition the input and call the algorithm recursively on one of the partitions, just like in quickselect.

In the case of dividing the array into five groups, we get the recurrence: $T(n)=T(n/5)+T(7n/10)$. That simply means that the value returned by partitioning is al least $3n/10−3/2$ and at most $7n/10+3/2$. However, what happens if we divide the array into 3 groups? What will be the upper and lower bounds? And what will be the recurrence of the runtime of the whole algo?

My thoughts: So the upper bound for $k=5$ is $7n/10 +3/2$. However, I do not understand where this $3/2$ come from? So for $k=3$ it should be like $2n/3 +?$. And also please explain what will be the lower bound? Thanks in advance.