prove n = Big-O(1) using induction

I know that the relation n = Big-O(1) is false. But if we use induction involving Big-O it can be proved. But the fallacy is we cannot induct Big-O. But my question is how we can disprove the relation by using the constants.

The false proof is here, please give me the proof of it being false using the constants. I'm getting confused with the constants, I don't know whether each relation used in the proof is having different constant or the same. Please enlighten on the topic.

TO prove: n= O(1)
for n=1 , 1= O(1) proved

induction hypothesis : let it is true : n-1 = O(1) now we prove that n = O(1)

LHS :  n = (n-1) + 1 
         =  O(1) + 1
         =  O(1开发者_运维问答) + O(1)
         =  O(1) 

Falsely proved.. I want the clarification of the fallacy in terms of <= and constants, that is in the basic definition of Big-O.

There is a huge logical fallacy hidden here:

LHS :  n = (n-1) + 1 
         =  O(1) + 1
         =  O(1) + O(1)
         =  O(1) 

n is a function and Ο(1) is a set of functions. Neither is a number (and induction proofs are all about proving things for a whole bunch of individual numbers in one fell swoop). The use of equal signs, like n = Ο(1), is an informal shorthand for f ∈ Ο(1), where f(x) = x.

This proof uses the fallacy of equivocation in two ways:

• by pretending that n is a number (the next number in the inductive journey) rather than an entire function
• by pretending the equal signs mean that two numbers are equal, which is what it means in an induction proof, instead of being a shorthand for element-of

If you want to see more clearly why this proof fails, replace n with another notation for a function, f (where f(x) = x), and the equal signs with element-of signs where needed and see if the proof still makes sense.

Base case:

let h(x) = 1 in
          h ∈ Ο(1)        [Any function is in Ο(that function)]

Inductive case:

          n = (n - 1) + 1 [Algebraic identity]
      n - 1 = n - 1       [Arithmetic]

let f(x) = x
    g(x) = f(x) - 1 in
          g ∈ Ο(1)        [Assume g ∈ Ο(1) because a different function, h, was]
          f ∈ Ο(1 + 1)    [By definition of Ο]
          f ∈ Ο(2)        [Arithmetic]

It becomes much clearer that this is not an induction proof at all. It's not even a valid proof in its own right, because we only proved that h ∈ Ο(1), which has nothing to do with whether g ∈ Ο(1), since those functions act very, very differently from each other.

The big O notation is about functions, so statements like 1 = O(1) have no meaning. What you are proving here is that if you take an arbitrary n and the constant function f(x) = n then f = O(1) which is true and gives no contradiction. There is no problem with the proof, the problem is that you are confusing the constant function f(x) = n with the function f(n) = n. For the latter we have that f = O(n) and if you try to prove it with your method you'll see that it won't work.

One thing you have to understand here is that Big-O or simply O denotes the 'rate' at which a function grows. You cannot use Mathematical induction to prove this particular property.

One example is

O(n^2) = O(n^2) + O(n)

By simple math, the above statement implies O(n) = 0 which is not. So I would say do not use MI for this. MI is more appropriate for absolute values.

If you need to do any rigorous proofs involving Big-O notation, you need to start with the format definition of Big-O In a proof you can't just say O(1) + 1 = O(1). You need to do the proof in terms of the formal definition. To prove that a function (f(n) = n for example) is O(1), you need to find unique x0 and M that match the definition. You can demonstrate this through induction, and you can also do a proof by contradiction using the definition to show that f(n) = n is not O(1)

Just as Olathe stated in his answer, you can't just add Big-O sets and functions. Start with the formal definition of what classifies a function as a member of a particular Big-O set.