Какова сложность алгоритма вычисления?

Question

[Расул Какушев]

Задан список городов. Известны их названия и регионы, однако неизвестны координаты. Алгоритм проходит по списку городов и каждый раз обращается к серверу, получая координаты или получая ошибку. В случае получения координат, они приписываются к городу и он удаляется из списка. Когда алгоритм доходит до конца, если в списке остались элементы, то рекурсивно вызывается функция для оставшегося списка. У меня подозрение что это O(n*log n)

Comments

[Stanislav Pugachev]

это в лучшем случае или в худшем?

[Расул Какушев]

И в том р в другом

[EVGENY T.]

Непонятно, откуда логорифм? Пока вижу S = N + (n-k1) + (n-k2)..., что = K*N, т.е. сложность выходит O(N).

[Расул Какушев]

EVGENY T., Я подумал что он из-за того что происходят ошибки пройдет по списку не один раз, а несколько, но с каждым разом список уменьшается)) Хотя вы правы.))