Как оценить время выполнения алгоритма О( )?
Как мне теперь убедится в том, что мой алгоритм действительно выполняется за время O(n)?
Так и убедиться:
Счетчик - n сложений
Проход по счетчику - константа (65тыс значений)
Выкладывание отсортированных чисел - n присваиваний
---------
Итого O(n)
То, что вы написали, называется сортировка подсчётом. Сложность действительно O(n), поскольку вы проходите по исходному массиву всего 1 раз.
Вы также проходите 2 раза и по массиву фиксированной длины (65536).
Общий анализ выглядит следующим образом:
65536 (заполнение нулями) + N (проход по исходному массиву для подсчёта элементов) + 65536 (проход по массиву счётчиков для записи в выходной, теперь уже отсортированный массив) = 2*65536 + N = O(N + 2*65536) = O(N).
В случае сортировки вставками вы в худшем случае делаете N операций (оценка грубая) для каждого из N элементов исходного массива: N*N=N^2=O(N^2).