я увеличил N до 1000000, но p так и осталось 963 при k=100. так что, видимо, моя асимптотика если и верная, то для очень больших k(и N соответственно). для реального же проекта N в районе от 10000 до 100000 (при использовании библиотек), а вот k у большого класса может быть и 100 (но это редкость). в этом случае наблюдается удесятерение виртуальной таблицы, а вот для среднего k=10 - всего лишь удвоение (упятерение в редких плохих случаях).

так что похоже это и правда работает.