Как спрогнозировать время работы программы?

Здравствуйте!

У меня возник следующий вопрос. Необходимо разработать алгоритм, который на среднем ПК давал бы приемлемый результат по времени работы.

При этом вероятность попадания в самый худший по времени случай крайне мала. Поэтому поставить метки для измерения работы программы в самом коде - не вариант.

Можно было бы измерить сложность алгоритма, допустим O(n^2), и взять худший n. Но даст ли это понятие о реальном затраченном времени?

Приведу пример: обычный двойной вложенный цикл

JavaВыделить код

1
2
3
4
5

for (i = 0; i < random.nextInt(1000000); i++) {
    for (j = 0; j < random.nextInt(1000000); j++) {
         System.out.println("i: " + i + "tj: " + j);
    }
}

Сложность: O

Максимальный n = 1000000

Максимальная сложность: 1000000^2. Вероятность этого случая: 1/1000000^2.

Соответственно, вопрос: как можно определить наихудшее время работы данного алгоритма на среднем ПК? Очевидно, что допускается приемлемая погрешность.

Заранее спасибо за ответы!