Let $x = n \mod 3$. Divide the input array A into 3 sections, with the left $x$ sections being $\lceil n/3 \rceil$ cells
large, and the right $3-x$ sections being $\lfloor n/3 \rfloor$ cells large. Suppose the $n/3$ largest values are in the
leftmost section. We need to move them to the rightmost section to achieve a sort.
This means they must pass through the middle section. The middle of A is either $n/3 + 1$ cells large, or $n/3$ cells large.
So to migrate through the middle section, $n/3 + 1$ or $n/3$ executions of line 6 are required. We have $n/3$ values to move
through the middle section. So that's either $(n/3 + 1)(n/3)$ or $(n/3)(n/3)$ executions of line 6 that are required.
These both amount to $Ω(n^2)$ cost, so the worst-case running time of InsertionSort is $Ω(n^2)$.
SelectionSort has an outer for loop and an inner one. The outer one always executes $n-1$ times. The inner one executes a number of times dependent on $i$, but the most it executes is $n$ times, when $i=1$. So the most SelectionSort costs is $(n-1)(n)$ times, which is less than $n^2$. The inner loop's execution time is constant. So the most it costs is a constant times $n^2$, or $O(n^2)$.
In any case, the inner loop still executes $n$ times when $i=1$. The outer loop still executes $n-1$ times. This means the algorithm's running time is at least proportional to $(n-1)(n)$, which is $Ω(n^2)$.
So SelectionSort's running time in any case is $θ(n^2)$.
Let $𝛼=x/y$ and $0 < 𝛼 < 1$. Let $n$ be a multiple of $y$ so that 𝛼n is an integer.
Suppose the largest $𝛼n$ values of the input array are in the
first $𝛼n$ array positions. $𝛼$ must be smaller than $1/2 - 1/(2n)$, so that there is at least one middle cell to move
items through. Then the $𝛼n$ largest values must move through the middle $(1-2𝛼)n$ array positions. That's $(𝛼n)(1-2𝛼)n = n^2(𝛼 - 2𝛼^2)$ invocations of line 6. This is at least $cn^2$ where $c=(𝛼-2𝛼^2)$, so InsertionSort is $Ω(n^2)$.
To determine the value of $𝛼$ that maximizes the number of times the largest 𝛼n values must move through the middle positions, we take
the first and second derivatives of the factor of $n^2$, $𝛼-2𝛼^2$.
$$
\begin{align}
d/d𝛼(𝛼-2𝛼^2) &= -4𝛼 + 1
\end{align}
$$
And the second derivative:
$$
\begin{align}
d/d𝛼(-4𝛼 + 1) &= -4
\end{align}
$$
Setting the first to 0 to find its critical points:
$$
\begin{align}
-4𝛼 + 1 &= 0 \\
1 &= 4𝛼 \\
1/4 &= 𝛼
\end{align}
$$
Since the second derivative is -4, this is a relative maximum.
So the value of $𝛼$ that optimizes the number of times the $𝛼n$ largest values must move through the middle $(1-2𝛼)n$ array positions is $𝛼=1/4$.
