У меня следующий вопрос:
Является ли следующее утверждение верным или неверным?
Все журналы базы 2
log2n является участникомO (log (n))
Моя попытка:
- log2n - clogn <= 0 </li>
- log2 + logn - clogn <= 0 </li>
- 1 + logn (1-c) <= 0 </li>
Теперь исправьте меня, если я ошибаюсь, но я должен найти значения для n (переменная) и c (постоянная), которые либо докажутили опровергнуть это ...
Обычно это кажется правдой:
Выберите
n0 = 2, c = 3 -> TRUE
n1 = 3, c = 3 -> TRUE
n2 = 4, c = 3 -> TRUE
Следовательно, утверждение кажется истинным, logn увеличивается, как и n.Но есть также значения, для которых вышеупомянутое утверждение никогда не будет выполняться:
например,
Выбор значения c = 1 больше нуля независимо от увеличения значения n.
Поэтому я не понимаю, правда это или нет ...