Эмпирическая оценка временной эффективности big-oh

Предыстория

Я хочу оценить производительность некоторых методов в библиотеке с помощью бенчмарков. Мне не нужна точность - достаточно показать, что что-то является O(1), O(logn), O(n), O(nlogn), O(n^2) или хуже этого. Поскольку big-oh означает верхнюю границу, оценка O(logn) для чего-то, что является O(log logn), не является проблемой.

Сейчас я думаю найти постоянный множитель k, который лучше всего подходит к данным для каждого big-oh (но будет превосходить все результаты), а затем выбрать big-oh с наилучшим подходом.

Вопросы

1. Есть ли лучшие способы сделать это, чем тот, о котором я думаю? Если да, то какие?
2. Иначе, может ли кто-нибудь указать мне на алгоритмы для оценки k для наилучшей подгонки и сравнения того, насколько хорошо каждая кривая подходит к данным?

Примечания и ограничения

Учитывая комментарии на данный момент, я должен прояснить несколько вещей:

• Это должно быть автоматизировано. Я не могу "посмотреть" на данные и принять решение.
• Я собираюсь сравнить методы с несколькими n размерами. Для каждого размера n я буду использовать проверенную систему эталонов, которая обеспечивает надежные статистические результаты.
• На самом деле я заранее знаю большую часть методов, которые будут тестироваться. Мое главное намерение - обеспечить для них регрессионное тестирование производительности.
• Код будет написан на Scala, можно использовать любую свободную библиотеку Java.

Пример

Вот один пример того, что я хочу измерить. У меня есть метод с такой сигнатурой:

def apply(n: Int): A

Учитывая n, он возвращает n-й элемент последовательности. Этот метод может иметь O(1), O(logn) или O(n), учитывая существующие реализации, и небольшие изменения могут заставить его по ошибке использовать неоптимальную реализацию. Или, что еще проще, можно заставить какой-то другой метод, который зависит от него, использовать его субоптимальную версию.