Как доказать это утверждение большой нотации?

Question

Как доказать это:

1. 4 ⁿ = O (8 ⁿ )
2. 8 ⁿ = O (4 ⁿ )?

Так, каковы значения C и n0 для обоих случаев?

Answer 1

РЕДАКТИРОВАТЬ: Я пытался уточнить, я немного больше ...

1. Для доказательства (см. формальное определение Big-O ) мы должны найти любые C и n0, которые 4 ⁿ <= C * 8 ​​<sup> n для всех n> n0. Итак, чтобы доказать ваш случай 1, это все о поиске примера для этих двух значений. Мы попробуем ... уравнение, которое я только что процитировал из википедии, гласит:

f(n) = O(g(n))

тогда и только тогда, когда существует положительное действительное число C и действительное число n0, такое что

|f(n)| <= C * |g(n)| for all n > n0

, где f (n) = 4 ⁿ и g (n) = 8 ⁿ

4^n    <= C * 8^n
4^n    <= C * 2^n * 4^n
1      <= C * 2^n

Поэтому мы выбираем C равным 1 и n0 равным 1. Уравнение верно -> доказан случай 1.

2. Так как я думаю, что это домашнее задание - вы должны попробовать сами - я могу помочь вам немного больше, как только вы предоставите результаты своих попыток.
Подсказка: просто попробуйте найти там C и n0 - возможно, вы сможете доказать, что никогда не существует пары C и n0 для уравнения ... ^^

Answer 2

Из того, что я помню о законе логарифмов:

log _b (x ^y ) = (y) log _b (x)

Я думаю, что это хорошая отправная точка. Я не собираюсь заканчивать, потому что это домашнее задание. ;)

UPDATE:

Чем больше я на это смотрю, тем больше я думаю, что чего-то не хватает в исходном вопросе. Определите, что C и n ₀ , для начинающих.