Question

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

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

Answer 1

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