Как доказать, что f(n)=Θ(g(n)) => f(n)=cg(n)+o(g(n))
Вопрос в том, чтобы доказать, верно ли следующее или нет.
f(n) = Θ(g(n)) => f(n) = cg(n) + o(g(n))для некоторой реальной константы c > 0,
примечание: о мало о
Я пытался сделать следующее:o(g(n)) средства <cg(n)для некоторой константы c
следовательно, cg(n) + cg(n) = 2cg(n) = cg(n) которая не является асимптотически жесткой
Итак R.H.S. является cg(n)<f(n)<cg(n) в то время как L.H.S. является cg(n)<= f(n) <= cg(n)так что иск ложный
Это законно?