Асимптотика vector erase

На сколько я знаю erase работает за линию, однако в задаче, которую я делал недавно, решение за n^2 log n (если считать, что erase работает за линию) прошло за 0.5 секунды. Что это, плохие тесты или у erase другая асимптотика? P.S erase использовал в векторе и удалял по итератору