Предположим, ** одной и той же машине проводится сравнительный анализ реализаций двух...

Question

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

Я так понимаю надо составить неравенство или что?

Answer 1

Вычислительная сложность алгоритма сортировки вставками в среднем оценивается как , а сортировки слиянием - в среднем оценивается как 
Нужно определить, при каком N первая оценка превысит вторую.
N*logN; \ N>logN \to N>0" alt="N^2>N*logN; \ N>logN \to N>0" align="absmiddle" class="latex-formula">
Получается, что в среднем сортировка слиянием всегда будет лучше сортировки вставками.