nput: A sequence A :$=($a$1,...,$ an$)$ of positive integers such that

$$ each element ai of A$,$ where i is divisible by $10,$ is in the sorted list of A at the correct

position;

$$ each element ai of A$,$ where i is divisible by $7,$ is in the sorted list of A either $($i$)$ at the

correct position or $($ii$)$ no more than one position away from its correct position.

For example, given a sequence A :$=($a$1,...,$ a$35),$ the position of the element a$30$ in the sorted list

of A is $30,$ and the possible positions of the element a$7$ in the sorted list would be $6,7,8.$

$(1)$ Obtain asymptotically tight bounds on lg$($n$!)$ without using Stirling$$s approximation. In$-$

stead, consider the summation Pn

k$=1$ lg k$.($Hint: Techniques from section A$\mathrm{.}2$ in the text$-$

book might be useful.$)$

$(2)$ Show that the $($n log n$)$ lower bound for the general comparison sort problem still holds

for the constrained input described above.

$1$