Я знаю, что отношение n = Big-O (1) неверно. Но если мы используем индукцию с участием Big-O, это можно доказать. Но заблуждение состоит в том, что мы не можем ввести Big-O. Но мой вопрос в том, как мы можем опровергнуть это отношение, используя константы.
Ложное доказательство здесь, пожалуйста, дайте мне доказательство того, что оно ложно, используя константы. Я путаюсь с константами, не понимаю Я не знаю, имеет ли каждое отношение, используемое в доказательстве, разную константу или одинаковую. Просветите, пожалуйста, по теме.
TO prove: n= O(1)
for n=1 , 1= O(1) proved
гипотеза индукции: пусть это правда: n-1 = O (1) Теперь мы докажем, что n = O (1)
LHS : n = (n-1) + 1
= O(1) + 1
= O(1) + O(1)
= O(1)
Доказано неверно. Я хочу пояснить ошибку в терминах <= и констант, которые содержатся в основном определении Big-O.