ME>Это действительно не константа, но ее время исполнения можно принять за константу, так как на каждой итерации он будет выполняться за константное время (если, конечно, размер твоего массива постоянен). Только если время выполнения memset будет равно времени исполнения одной итерации (что, как мне кажется, маловероятно), memset сможет повысить степень выражения асимптоматической сложности алгоритма.
1) Сложность алгоритма считается в наихудшем и асимптотическая ( в O()).
2) Размер P-массива равен n — и n может (считаем поведение на бесконечности) быть оЧень большим
3) Насколько я понимаю, memset есть (буквально)"оптимизированная версия пробежать первых n байт и заполнить их фиксированным значением". Т.е. ты говоришь, что он просто очень быстрый (если n-мало), не более того.
