"Думал сначала парсить комментарии, собирая в словарь с ключами ID новостей, но там у меня вышел так же цикл в цикле N*M"
почему? сначала парсим все комментарии в словарь
это M операций
потом идем по всем новостям - это N операций
итого N + M
где тут цикл в цикле?