докажите, что n = Big-O (1) с помощью индукции

Я знаю, что отношение 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.

7
задан Bill the Lizard 19 September 2012 в 22:22
поделиться