\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[russian]{babel}
\usepackage{amsmath,amssymb}

% Шаблон домашнего задания к лекции 3 (условие — hw-lecture.ipynb на сайте недели).
% Соберите PDF где получится (онлайн-компилятор или локальный TeX).
% Лектору пришлите этот .tex и получившийся PDF.
% Семинаристу это задание не отправляйте.
% Код программы присылать не нужно.

\title{Домашнее задание к лекции 3\\Сортировки. Инварианты циклов}
\author{Фамилия Имя Отчество, группа \texttt{XXXX}}
\date{}

\begin{document}

\maketitle

\noindent
Подбросьте монетку и разберите \textbf{ровно тот} алгоритм, который выпал.
Не выбирайте сами.

\begin{itemize}
	\item орёл --- сортировка \textbf{вставками};
	\item решка --- сортировка \textbf{выбором}.
\end{itemize}

Выпало: \underline{\hspace{3cm}}\qquad
разбираю: \underline{\hspace{5cm}}.

\noindent
Образец оформления --- файл \texttt{lsd-example.tex} в папке недели (псевдокод, зачем метод, инвариант, время и память).
Тема вашего текста --- вставки или выбор, не LSD и не пузырёк.

\section*{Инвариант}

Своими словами: что верно про префикс или хвост массива после очередного шага внешнего цикла.
Ниже --- пример, как записывать формулы; замените его своим текстом.

\begin{align*}
	&\text{после шага } k \text{ верно, что } \ldots \\
	&\text{в худшем случае время } T(n) = \Theta(\ldots) \\
	&\text{дополнительная память } M(n) = \Theta(\ldots)
\end{align*}

\section*{Трассировка}

Возьмите массив из пяти чисел (свой или, например, $[4,\,1,\,3,\,5,\,2]$).
Один шаг --- итерация внешнего цикла: префикс длиннее на единицу.
Выпишите $4$--$5$ таких шагов: что сравнивали, что меняли или сдвигали, каким стал массив.

Массив до начала: $[\,\ldots\,]$.

\begin{enumerate}
	\item Шаг 1.
	\item Шаг 2.
	\item Шаг 3.
	\item Шаг 4.
	\item Шаг 5 (если нужен).
\end{enumerate}

\section*{Чем это не пузырёк}

Одной--тремя фразами: какой инвариант у вашего алгоритма и почему это не «после $k$ прогонов хвост из $k$ максимумов уже на месте».

\end{document}