4 replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
source | link

I was not careful and assumed a standard implementation of minimum, not the one given in the question. Hence, the answer below solves a much simpler problem.


Intuition: The algorithm is Selection Sort with a weird way to select the minimum; it can take quadratic time. That is, the algorithm takes cubic time in the worst case.

Following the structured method outlined in our reference questionstructured method outlined in our reference question on this Broken Selection Sort, you arrive at something like this:

$\qquad\begin{align*} T(\mathtt{[] | [x]}) &= d, \\ T(\mathtt{x::xs}) &= cn + \begin{cases} T(\mathtt{xs}), & \mathtt{x = min(x::xs)}; \\ T(\mathtt{xs@[x]}, &\text{else}. \end{cases} \end{align*}$

I assume some cost measure that is related to list operations. Note that I introduce $cn$ for the (dominant term) of the toll function, which covers minimum, head and tail, as well as the other operations. We'll see that the constant factor is relevant. The one in the anchor turns out not to be, though.

Now, in order to get a lower bound on the worst-case cost we can fix any input. Let us consider the reversely sorted list. Given such a list with $n$ elements, we hit case two $n-1$ times; then the originally last element (the minimum) is in front and we hit case one. In this case, $\mathtt{xs}$ is a reversely sorted list again, so we can set up the following recurrence:

$\qquad\begin{align*} T'(\leq 1) &= d, \\ T'(n) &= n \cdot cn + T'(n-1). \end{align*}$

SolvingSolving this we get that

$\qquad T'(n) = cn^3 + d \in \Theta(n^3)$,

which implies that

$\qquad T_{\mathrm{WC}}(n) \in \Omega(n^3)$.

Since no list can cause case two hit more than $n-1$ times per removed ($n$th-largest) element, this bound is tight; $T_{\mathrm{WC}}(n) \in \Theta(n^3)$.

FWIW, not much changes if you consider the average case. The toll function will then be $c \cdot \operatorname{rank}(\mathtt{x}, \mathtt{x::xs})$. In the random permutation model, the expected rank of $\mathtt{x}$ is $\frac{n}{2}$, and the model applies recursively. That is, $c$ changes in expectation, but the $\Theta$-class does not change.

I was not careful and assumed a standard implementation of minimum, not the one given in the question. Hence, the answer below solves a much simpler problem.


Intuition: The algorithm is Selection Sort with a weird way to select the minimum; it can take quadratic time. That is, the algorithm takes cubic time in the worst case.

Following the structured method outlined in our reference question on this Broken Selection Sort, you arrive at something like this:

$\qquad\begin{align*} T(\mathtt{[] | [x]}) &= d, \\ T(\mathtt{x::xs}) &= cn + \begin{cases} T(\mathtt{xs}), & \mathtt{x = min(x::xs)}; \\ T(\mathtt{xs@[x]}, &\text{else}. \end{cases} \end{align*}$

I assume some cost measure that is related to list operations. Note that I introduce $cn$ for the (dominant term) of the toll function, which covers minimum, head and tail, as well as the other operations. We'll see that the constant factor is relevant. The one in the anchor turns out not to be, though.

Now, in order to get a lower bound on the worst-case cost we can fix any input. Let us consider the reversely sorted list. Given such a list with $n$ elements, we hit case two $n-1$ times; then the originally last element (the minimum) is in front and we hit case one. In this case, $\mathtt{xs}$ is a reversely sorted list again, so we can set up the following recurrence:

$\qquad\begin{align*} T'(\leq 1) &= d, \\ T'(n) &= n \cdot cn + T'(n-1). \end{align*}$

Solving this we get that

$\qquad T'(n) = cn^3 + d \in \Theta(n^3)$,

which implies that

$\qquad T_{\mathrm{WC}}(n) \in \Omega(n^3)$.

Since no list can cause case two hit more than $n-1$ times per removed ($n$th-largest) element, this bound is tight; $T_{\mathrm{WC}}(n) \in \Theta(n^3)$.

FWIW, not much changes if you consider the average case. The toll function will then be $c \cdot \operatorname{rank}(\mathtt{x}, \mathtt{x::xs})$. In the random permutation model, the expected rank of $\mathtt{x}$ is $\frac{n}{2}$, and the model applies recursively. That is, $c$ changes in expectation, but the $\Theta$-class does not change.

I was not careful and assumed a standard implementation of minimum, not the one given in the question. Hence, the answer below solves a much simpler problem.


Intuition: The algorithm is Selection Sort with a weird way to select the minimum; it can take quadratic time. That is, the algorithm takes cubic time in the worst case.

Following the structured method outlined in our reference question on this Broken Selection Sort, you arrive at something like this:

$\qquad\begin{align*} T(\mathtt{[] | [x]}) &= d, \\ T(\mathtt{x::xs}) &= cn + \begin{cases} T(\mathtt{xs}), & \mathtt{x = min(x::xs)}; \\ T(\mathtt{xs@[x]}, &\text{else}. \end{cases} \end{align*}$

I assume some cost measure that is related to list operations. Note that I introduce $cn$ for the (dominant term) of the toll function, which covers minimum, head and tail, as well as the other operations. We'll see that the constant factor is relevant. The one in the anchor turns out not to be, though.

Now, in order to get a lower bound on the worst-case cost we can fix any input. Let us consider the reversely sorted list. Given such a list with $n$ elements, we hit case two $n-1$ times; then the originally last element (the minimum) is in front and we hit case one. In this case, $\mathtt{xs}$ is a reversely sorted list again, so we can set up the following recurrence:

$\qquad\begin{align*} T'(\leq 1) &= d, \\ T'(n) &= n \cdot cn + T'(n-1). \end{align*}$

Solving this we get that

$\qquad T'(n) = cn^3 + d \in \Theta(n^3)$,

which implies that

$\qquad T_{\mathrm{WC}}(n) \in \Omega(n^3)$.

Since no list can cause case two hit more than $n-1$ times per removed ($n$th-largest) element, this bound is tight; $T_{\mathrm{WC}}(n) \in \Theta(n^3)$.

FWIW, not much changes if you consider the average case. The toll function will then be $c \cdot \operatorname{rank}(\mathtt{x}, \mathtt{x::xs})$. In the random permutation model, the expected rank of $\mathtt{x}$ is $\frac{n}{2}$, and the model applies recursively. That is, $c$ changes in expectation, but the $\Theta$-class does not change.

3 added 187 characters in body
source | link

I was not careful and assumed a standard implementation of minimum, not the one given in the question. Hence, the answer below solves a much simpler problem.


Intuition: The algorithm is Selection Sort with a weird way to select the minimum; it can take quadratic time. That is, the algorithm takes cubic time in the worst case.

Following the structured method outlined in our reference question on this Broken Selection Sort, you arrive at something like this:

$\qquad\begin{align*} T(\mathtt{[] | [x]}) &= d, \\ T(\mathtt{x::xs}) &= cn + \begin{cases} T(\mathtt{xs}), & \mathtt{x = min(x::xs)}; \\ T(\mathtt{xs@[x]}, &\text{else}. \end{cases} \end{align*}$

I assume some cost measure that is related to list operations. Note that I introduce $cn$ for the (dominant term) of the toll function, which covers minimum, head and tail, as well as the other operations. We'll see that the constant factor is relevant. The one in the anchor turns out not to be, though.

Now, in order to get a lower bound on the worst-case cost we can fix any input. Let us consider the reversely sorted list. Given such a list with $n$ elements, we hit case two $n-1$ times; then the originally last element (the minimum) is in front and we hit case one. In this case, $\mathtt{xs}$ is a reversely sorted list again, so we can set up the following recurrence:

$\qquad\begin{align*} T'(\leq 1) &= d, \\ T'(n) &= (n-1) \cdot cn + T'(n-1) \cdot cn. \end{align*}$$\qquad\begin{align*} T'(\leq 1) &= d, \\ T'(n) &= n \cdot cn + T'(n-1). \end{align*}$

Solving this -- I used computer algebra¹ -- we get that

$\qquad T'(n) \in \Theta(c^n \cdot n!)$$\qquad T'(n) = cn^3 + d \in \Theta(n^3)$,

which implies that

$\qquad T_{\mathrm{WC}}(n) \in \Omega(c^n \cdot n!)$.

The constant factor hidden in the Landau symbols depends on $c$ and $d$$\qquad T_{\mathrm{WC}}(n) \in \Omega(n^3)$.

Since no list can cause case two hit more than $n-1$ times per removed ($n$th-largest) element, this bound is tight; $T_{\mathrm{WC}}(n) \in \Theta(c^n \cdot n!)$$T_{\mathrm{WC}}(n) \in \Theta(n^3)$.

FWIW, not much changes if you consider the average case. The toll function will then be $c \cdot \operatorname{rank}(\mathtt{x}, \mathtt{x::xs})$. In the random permutation model, the expected rank of $\mathtt{x}$ is $\frac{n}{2}$, and the model applies recursively. That is, $c$ changes in expectation, but the factor $n!$ remains$\Theta$-class does not change.


  1. In fact, for $n \geq 2$ we have

    $\qquad T'(n) = (cd + e^{\frac{1}{c}} - 1) \cdot c^{n-1} \cdot n!$

    as per the following Mathematica code:

    RSolve[T[n] == (n - 1)*c*n + T[n - 1]*c*n, T[n], n] 
    FullSimplify[%, Assumptions -> n \[Element] Integers && n >= 2]
    Limit[(T[n] /. %)[[1]]/(Factorial[n]*c^n), n -> Infinity]
    

Following the structured method outlined in our reference question on this Broken Selection Sort, you arrive at something like this:

$\qquad\begin{align*} T(\mathtt{[] | [x]}) &= d, \\ T(\mathtt{x::xs}) &= cn + \begin{cases} T(\mathtt{xs}), & \mathtt{x = min(x::xs)}; \\ T(\mathtt{xs@[x]}, &\text{else}. \end{cases} \end{align*}$

I assume some cost measure that is related to list operations. Note that I introduce $cn$ for the (dominant term) of the toll function, which covers minimum, head and tail, as well as the other operations. We'll see that the constant factor is relevant. The one in the anchor turns out not to be, though.

Now, in order to get a lower bound on the worst-case cost we can fix any input. Let us consider the reversely sorted list. Given such a list with $n$ elements, we hit case two $n-1$ times; then the originally last element (the minimum) is in front and we hit case one. In this case, $\mathtt{xs}$ is a reversely sorted list again, so we can set up the following recurrence:

$\qquad\begin{align*} T'(\leq 1) &= d, \\ T'(n) &= (n-1) \cdot cn + T'(n-1) \cdot cn. \end{align*}$

Solving this -- I used computer algebra¹ -- we get that

$\qquad T'(n) \in \Theta(c^n \cdot n!)$,

which implies that

$\qquad T_{\mathrm{WC}}(n) \in \Omega(c^n \cdot n!)$.

The constant factor hidden in the Landau symbols depends on $c$ and $d$.

Since no list can cause case two hit more than $n-1$ times per removed ($n$th-largest) element, this bound is tight; $T_{\mathrm{WC}}(n) \in \Theta(c^n \cdot n!)$.

FWIW, not much changes if you consider the average case. The toll function will then be $c \cdot \operatorname{rank}(\mathtt{x}, \mathtt{x::xs})$. In the random permutation model, the expected rank of $\mathtt{x}$ is $\frac{n}{2}$, and the model applies recursively. That is, $c$ changes in expectation, but the factor $n!$ remains.


  1. In fact, for $n \geq 2$ we have

    $\qquad T'(n) = (cd + e^{\frac{1}{c}} - 1) \cdot c^{n-1} \cdot n!$

    as per the following Mathematica code:

    RSolve[T[n] == (n - 1)*c*n + T[n - 1]*c*n, T[n], n] 
    FullSimplify[%, Assumptions -> n \[Element] Integers && n >= 2]
    Limit[(T[n] /. %)[[1]]/(Factorial[n]*c^n), n -> Infinity]
    

I was not careful and assumed a standard implementation of minimum, not the one given in the question. Hence, the answer below solves a much simpler problem.


Intuition: The algorithm is Selection Sort with a weird way to select the minimum; it can take quadratic time. That is, the algorithm takes cubic time in the worst case.

Following the structured method outlined in our reference question on this Broken Selection Sort, you arrive at something like this:

$\qquad\begin{align*} T(\mathtt{[] | [x]}) &= d, \\ T(\mathtt{x::xs}) &= cn + \begin{cases} T(\mathtt{xs}), & \mathtt{x = min(x::xs)}; \\ T(\mathtt{xs@[x]}, &\text{else}. \end{cases} \end{align*}$

I assume some cost measure that is related to list operations. Note that I introduce $cn$ for the (dominant term) of the toll function, which covers minimum, head and tail, as well as the other operations. We'll see that the constant factor is relevant. The one in the anchor turns out not to be, though.

Now, in order to get a lower bound on the worst-case cost we can fix any input. Let us consider the reversely sorted list. Given such a list with $n$ elements, we hit case two $n-1$ times; then the originally last element (the minimum) is in front and we hit case one. In this case, $\mathtt{xs}$ is a reversely sorted list again, so we can set up the following recurrence:

$\qquad\begin{align*} T'(\leq 1) &= d, \\ T'(n) &= n \cdot cn + T'(n-1). \end{align*}$

Solving this we get that

$\qquad T'(n) = cn^3 + d \in \Theta(n^3)$,

which implies that

$\qquad T_{\mathrm{WC}}(n) \in \Omega(n^3)$.

Since no list can cause case two hit more than $n-1$ times per removed ($n$th-largest) element, this bound is tight; $T_{\mathrm{WC}}(n) \in \Theta(n^3)$.

FWIW, not much changes if you consider the average case. The toll function will then be $c \cdot \operatorname{rank}(\mathtt{x}, \mathtt{x::xs})$. In the random permutation model, the expected rank of $\mathtt{x}$ is $\frac{n}{2}$, and the model applies recursively. That is, $c$ changes in expectation, but the $\Theta$-class does not change.

2 added 187 characters in body
source | link

Following the structured method outlined in our reference question on this Broken Selection Sort, you arrive at something like this:

$\qquad\begin{align*} T(\mathtt{[] | [x]}) &= d, \\ T(\mathtt{x::xs}) &= cn + \begin{cases} T(\mathtt{xs}), & \mathtt{x = min(x::xs)}; \\ T(\mathtt{xs@[x]}, &\text{else}. \end{cases} \end{align*}$

I assume some cost measure that is related to list operations. Note that I introduce $cn$ for the (dominant term) of the toll function, which covers minimum, head and tail, as well as the other operations. We'll see that the constant factor is relevant. The one in the anchor turns out not to be, though.

Now, in order to get a lower bound on the worst-case cost we can fix any input. Let us consider the reversely sorted list. Given such a list with $n$ elements, we hit case two $n-1$ times; then the originally last element (the minimum) is in front and we hit case one. In this case, $\mathtt{xs}$ is a reversely sorted list again, so we can set up the following recurrence:

$\qquad\begin{align*} T'(\leq 1) &= d, \\ T'(n) &= (n-1) \cdot cn + T'(n-1) \cdot cn. \end{align*}$

Solving this -- I used computer algebra¹ -- we get that

$\qquad T'(n) \in \Theta(c^n \cdot n!)$,

which implies that

$\qquad T_{\mathrm{WC}}(n) \in \Omega(c^n \cdot n!)$.

The constant factor hidden in the Landau symbols depends on $c$ and $d$.

Since no list can cause case two hit more than $n-1$ times per removed ($n$th-largest) element, this bound is tight; $T_{\mathrm{WC}}(n) \in \Theta(c^n \cdot n!)$.

FWIW, not much changes if you consider the average case. The toll function will then be $c \cdot \operatorname{rank}(\mathtt{x}, \mathtt{x::xs})$. In the random permutation model, the expected rank of $\mathtt{x}$ is $\frac{n}{2}$, and the model applies recursively. That is, $c$ changes in expectation, but the factor $n!$ remains.


  1. In fact, for $n \geq 2$ we have

    $\qquad T'(n) = (cd + e^{\frac{1}{c}} - 1) \cdot c^{n-1} \cdot n!$

    as per the following Mathematica code:

    RSolve[T[n] == (n - 1)*c*n + T[n - 1]*c*n, T[n], n] 
    FullSimplify[%, Assumptions -> n \[Element] Integers && n >= 2]
    Limit[(T[n] /. %)[[1]]/(Factorial[n]*c^n), n -> Infinity]
    

Following the structured method outlined in our reference question on this Broken Selection Sort, you arrive at something like this:

$\qquad\begin{align*} T(\mathtt{[] | [x]}) &= d, \\ T(\mathtt{x::xs}) &= cn + \begin{cases} T(\mathtt{xs}), & \mathtt{x = min(x::xs)}; \\ T(\mathtt{xs@[x]}, &\text{else}. \end{cases} \end{align*}$

I assume some cost measure that is related to list operations. Note that I introduce $cn$ for the (dominant term) of the toll function, which covers minimum, head and tail, as well as the other operations. We'll see that the constant factor is relevant. The one in the anchor turns out not to be, though.

Now, in order to get a lower bound on the worst-case cost we can fix any input. Let us consider the reversely sorted list. Given such a list with $n$ elements, we hit case two $n-1$ times; then the originally last element (the minimum) is in front and we hit case one. In this case, $\mathtt{xs}$ is a reversely sorted list again, so we can set up the following recurrence:

$\qquad\begin{align*} T'(\leq 1) &= d, \\ T'(n) &= (n-1) \cdot cn + T'(n-1) \cdot cn. \end{align*}$

Solving this -- I used computer algebra¹ -- we get that

$\qquad T'(n) \in \Theta(c^n \cdot n!)$,

which implies that

$\qquad T_{\mathrm{WC}}(n) \in \Omega(c^n \cdot n!)$.

The constant factor hidden in the Landau symbols depends on $c$ and $d$.

Since no list can cause case two hit more than $n-1$ times per removed ($n$th-largest) element, this bound is tight; $T_{\mathrm{WC}}(n) \in \Theta(c^n \cdot n!)$.

FWIW, not much changes if you consider the average case. The toll function will then be $c \cdot \operatorname{rank}(\mathtt{x}, \mathtt{x::xs})$


  1. In fact, for $n \geq 2$ we have

    $\qquad T'(n) = (cd + e^{\frac{1}{c}} - 1) \cdot c^{n-1} \cdot n!$

    as per the following Mathematica code:

    RSolve[T[n] == (n - 1)*c*n + T[n - 1]*c*n, T[n], n] 
    FullSimplify[%, Assumptions -> n \[Element] Integers && n >= 2]
    Limit[(T[n] /. %)[[1]]/(Factorial[n]*c^n), n -> Infinity]
    

Following the structured method outlined in our reference question on this Broken Selection Sort, you arrive at something like this:

$\qquad\begin{align*} T(\mathtt{[] | [x]}) &= d, \\ T(\mathtt{x::xs}) &= cn + \begin{cases} T(\mathtt{xs}), & \mathtt{x = min(x::xs)}; \\ T(\mathtt{xs@[x]}, &\text{else}. \end{cases} \end{align*}$

I assume some cost measure that is related to list operations. Note that I introduce $cn$ for the (dominant term) of the toll function, which covers minimum, head and tail, as well as the other operations. We'll see that the constant factor is relevant. The one in the anchor turns out not to be, though.

Now, in order to get a lower bound on the worst-case cost we can fix any input. Let us consider the reversely sorted list. Given such a list with $n$ elements, we hit case two $n-1$ times; then the originally last element (the minimum) is in front and we hit case one. In this case, $\mathtt{xs}$ is a reversely sorted list again, so we can set up the following recurrence:

$\qquad\begin{align*} T'(\leq 1) &= d, \\ T'(n) &= (n-1) \cdot cn + T'(n-1) \cdot cn. \end{align*}$

Solving this -- I used computer algebra¹ -- we get that

$\qquad T'(n) \in \Theta(c^n \cdot n!)$,

which implies that

$\qquad T_{\mathrm{WC}}(n) \in \Omega(c^n \cdot n!)$.

The constant factor hidden in the Landau symbols depends on $c$ and $d$.

Since no list can cause case two hit more than $n-1$ times per removed ($n$th-largest) element, this bound is tight; $T_{\mathrm{WC}}(n) \in \Theta(c^n \cdot n!)$.

FWIW, not much changes if you consider the average case. The toll function will then be $c \cdot \operatorname{rank}(\mathtt{x}, \mathtt{x::xs})$. In the random permutation model, the expected rank of $\mathtt{x}$ is $\frac{n}{2}$, and the model applies recursively. That is, $c$ changes in expectation, but the factor $n!$ remains.


  1. In fact, for $n \geq 2$ we have

    $\qquad T'(n) = (cd + e^{\frac{1}{c}} - 1) \cdot c^{n-1} \cdot n!$

    as per the following Mathematica code:

    RSolve[T[n] == (n - 1)*c*n + T[n - 1]*c*n, T[n], n] 
    FullSimplify[%, Assumptions -> n \[Element] Integers && n >= 2]
    Limit[(T[n] /. %)[[1]]/(Factorial[n]*c^n), n -> Infinity]
    
1
source | link