Сложность нескольких переменных

Question

Я искал некоторые утверждения True / False для некоторых нотаций Big-O с несколькими переменными и придумал это ниже

n^k ∈ O(k^n) - false

Я не мог разобраться с этим утверждением, и мне нужны пояснения.

Объяснение выглядит как

если n выбрано фиксированным значением, а k → ∞, то левая часть уравнения становится экспоненциальной, тогда как правая часть является полиномиальной. Следовательно, n ^ k не ограничено k ^ n

Заключение становится ясным, когда n выбрано постоянным и k → ∞, но почему мы не можем поступить наоборот, то есть выбрать k в качестве константы и n → ∞? Что является рациональным в выборе n в качестве постоянной здесь?

Answer 1

Действительно, основываясь на определении, вы должны проверить оба случая. В этом доказательстве, поскольку одно из них не выполнено, мы можем сказать, что n^k не входит в O(k^n) для любых k и n. Хотя другая сторона верна, если вы берете k в качестве константы (>1) и n уходит в бесконечность.