1. Engineering
  2. Computer Science
  3. explain why the proof below is incorrect this proof uses...

Question: explain why the proof below is incorrect this proof uses...

Question details

Explain why the proof below is incorrect. This proof uses induction to prove the false claim that n2 - O(n) Hint: plug k - 1 (and maybe k - 2) into the inductive step and see where the argument breaks down (i.e., why it doesnt prove the formal definition) Proof. We prove that there exists some positive constant c such that n2< cn for all n2 1 by induction on n (Base case: n 1) When n-1, n2-n. Hence, n2 < cn for n 1 and (Inductive step) Suppose that there exists some positive c such that k2< ck, for some k 1, and consider (k + 1)2. Since c is positive, there are two possibilities: c 1/3 and c< 1/3 (Case 1: c 1/3) Note that since k 1, 2 2 k, so k < k2. Also, since SO(2 2k 1 21.2 3k2 1 53(ck) + 1 k2 ck 1 < 3c 3c(k 1)Hence, in the case where c > 1/3, there exists some positive constant c2, namely c2 3c, such that (k1)2 2(k1) (Case 2: c-1/3) If 1/3: (1)22 2k 1 2 3k2 + 1 2 OS 1/3 Hence, in the case where c < 1/3, there exists some positive constant c2 namely c2 1, such that (k1)2 c2(k +1) Since there exists some positive constant c2 such that k12 c2(k+1) in both cases, there exists some positive constant c such that n2-cn for all n 2 1, by induction. Thus, there exists positive constants c and no such that n2 < cn for all n no, namely c c and no -1. By the formal definition of Big-Oh, this means that nO(n)

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution