Доказательство простое.Предположим, p(y) = an y^k + ... + a1 y + a0.Как y = O(x), существует константа c, которая y < c*x.Следовательно, p(y) < an*c^k x^k + + ... + a1*c x + a0 = f(x).Если c <= 1, p(y) < p(x) как f(x) <= p(x).Если c > 1, мы можем сказать p(y) < c^k p(x).Следовательно, существует постоянная c' = c^k такая, что p(y) < c' p(x).Следовательно, p(y) = O(p(x)).
В конечном итоге, как z = O(p(y)), мы доказали, что z = O(p(x)).
Чтобы получить более точное доказательство, вы можете использовать математическую индукцию по степени полинома p(x).
Чтобы обобщить случай, мы должны попытаться найти, что функции с определеннымсвойство, которое f(y) < c' f(x), если y < c x.Одной из больших категорий функций является f(x), которая увеличивается, и f(cx) = \Theta(f(x)).Следовательно, транзитивность будет выполняться для всех этих функций.Например, f(x) = sqrt(x) удовлетворяет ограничению, но f(x) = 2^x нет.