Сложность (расчет большого О)

Question

Я работал над некоторыми проблемами в моем учебнике, которые касаются вычисления сложности алгоритмов. На один из вопросов, на который я поставлен вопрос, ответа нет, и я был бы признателен за любые комментарии.

У вас есть массив длины n-1, содержащий связанные списки, которые содержат списки слов. Каждый связанный список сначала сортируется по вставке, а затем, используя первое слово в связанном списке, массив сортируется быстро. Какова большая сложность этого алгоритма?

Я уже знаю, что:

Обход связанного списка - O (n) сортировка вставки O (n ^ 2) Быстрая сортировка (nlogn)

Я просто не уверен, как рассчитать сложность всего алгоритма

Answer 1

"каждый связанный список отсортирован по первой вставке"

Это усложняет O(n) * O(m^2) или O(n*m^2) - мы должны использовать другую букву, потому что длина каждого списка не связана с количеством списков.

"тогда массив будет отсортирован"

Это добавляет O(n log n).

Итого: O(n*m^2 + n log n), что упрощается до O(n*m^2) (n log n несущественно по сравнению с n*m^2).