Сравнить эффективность алгоритмов

[JMH]

Имеется семейство множеств $X_i$, каждое из которых содержит произвольное конечное число элементов. Имеется два алгоритма, выполняющих некоторое (одинаковое для обоих алгоритмов) вычисление на данном семействе; первый алгоритм занимает время, пропорциональное $\displaystyle\sum_{i=0}{|X_i|}$, второй - $|X_0|\displaystyle\sum_{i=1}{\log_2|X_i|}$. Не могу сообразить, как выбрать более эффективный алгоритм - о колличестве элементов множеств семейства ничего не известно.
Заранее благодарен за любые советы.

[worm2]

Чаще всего при теоретическом исследовании алгоритма интересуются поведением при $|X_i|\to\infty$. В нашем случае ситуация осложняется тем, что этих $X_i$ несколько, и каждое из них может стремиться к бесконечности со своей скоростью, независимой от остальных. Если, например, $|X_0|$ растёт существенно медленнее остальных (или вообще константа), то ответ очевиден. Если совсем наоборот — он тоже очевиден, но другой.

Для практических же целей нужно проводить эксперименты на данных, похожих на реальные.

-- Вт мар 12, 2013 11:12:55 --

Если же ну прямо уж совсем-совсем

JMH писал(а):

о количестве элементов множеств семейства ничего не известно

, то ничего нельзя сказать. Что больше: $A$ или $B\log A$ ? В такой общей постановке ответа нет.

[JMH]

Спасибо.