Предположим, на одной и той же машине проводится сравнительный анализ реализаций двух алгоритмов сортировки, работающих вставкой и слиянием. Длясортировки n элементов вставкой необходимо  шагов, а для сортировки слиянием необхо...

Вычислительная сложность алгоритма сортировки вставками в среднем оценивается как [latex]O_1=O(N^2)[/latex], а сортировки слиянием - в среднем оценивается как [latex]O_2=N\times logN[/latex] Нужно определить, при каком N первая оценка превысит вторую. [latex]N^2>N*logN; \ N>logN \to N>0[/latex] Получается, что в среднем сортировка слиянием всегда будет лучше сортировки вставками.