плавно увеличивать N и замерять время работы алгоритма в различных попугаях ?

100-120-144-172-207...-1000000000000

InterloperИ как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?Постройте два графика: получившийся и предполагаемый. Сделайте сравнение в пределах погрешности.

InterloperНасколько большое N нужно брать для графика?Зависит от того, под какие данные рассчитан алгоритм.

Если речь идет про простую сферическую в вакууме сортировку уровня студенческих лабораторных, то я бы сказал, что достаточно взять до миллиона элементов.

Просто бывают алгоритмы, к примеру тех же сортировок, рассчитанных на сортировку малых массивов, скажем, до 20 элементов. И гонять такой алгоритм даже на 100 элементах уже кощунство.

InterloperВ том то и дело, что мы не знаем как устроен алгоритм внутри.
Если у алгоритма нет генератора случайных чисел в виде одного из параметров "работы", то пройдитесь от 1 до 2^K, каждый раз увеличивая размер чисел вдвое. Делая несколько замеров на каждом N, с разными входными данными. Верхний предел - простое любопытство, время, при котором компьютер будет гонять алгоритм достаточно продолжительное для вашего ожидания время. В некоторых случаях это могут и быть и сутки, но для простых замеров достаточно, чтобы алгоритм работал одну-две минуты.

Если есть генератор случайных чисел и он определяет сложность, и погрешность при этом велика, то никак вы не определите, что там внутри. Для одних и тех же данных время может различаться, либо различаться не на одних и тех же, а скажем на соседних данных (с точки зрения алгоритма). Например, 2+2 будет складываться одну минуту, а 2+3 уже пятнадцать минут.