complexity theory - prove n = Big-O(1) using induction -


I know that relationship n = big-o (1) is wrong but if we want to include big-o It can prove if you use induction. But corruption can not be included in the big-o, but my question is how can we reject the relationship using constants.

False evidence is here, please give me proof of this being false using constants. I am confused with the constants, I do not know that each relation in the evidence is different or the same. Please highlight the subject.

  To prove: n = o (1) for n = 1, 1 = o (1) proven  

Induction hypothesis: this truth Now we prove that n = o (1)

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

proved wrong. I explained the reasoning of the argument & lt; = And in the case of constants, in the basic definition of Big-O.

There is a huge logical illusion that is hidden here:

n function and omicron; (1) There is neither a set of work nor a number (and the induction proof is about to prove things for a whole number of the same person who shocks one in the other).

  • Indicates that n is a number (the next one), the use of equal signals, such as n = & Omicron; (1).

    / Ul>

    If you want to see more clearly why this evidence fails, replace the n with another marking for a function, f (where f (x) = x), and Identical sign signs with elements where necessary and see whether the evidence still makes sense

    base case:

     f (h) = in h (x) = 1; & Omicron; (1) [any function is in the omicron; (That function)] 

    inductive matter:

     n = (n - 1) + 1 [algebraic identity] n - 1 = n - 1 [arithmetic] f (x) = XG (X) = F (X) - G and ICE in G; & Omicron; (1) [eclipse; & Omicron; (1) Because there was a different function, H, F]; & Omicron; (1 + 1) [And by definition of Omicron;] F & ISIN; & Omicron; (2) [arithmetic] 

    It becomes very clear that this is not an induction proof at all. It is not a valid proof in itself, because we have only proved that H & I; & Omicron; (1), in which there is no relation with G and ISIN; & Omicron; (1), because these functions work very differently from each other.


Comments