Error in "proof" of $n^2 \in O(n)$.

Question

I need some help. I have homework:

I need to disprove that $f(n^2)$ belongs to $O(n)$.

Why in question $n^2 = (n-1)^2+2n-1$? It must be $(n-1)^2-2n+1$. Am I right?

Answer 1

the error is that your "c" isn't a constant because it depends on "n", "c" must be constant over all n.

It seems that, in your proof, c = 2*n-1, so your "c" is not a constant.

Answer 2

The proof is flawed because for $f(n)$ to be $O(n)$, it must hold that $f(n) \le cn$ with the same c for each n. $c \ne c + 2$.

Answer 3

Answering the question given by OP himself not by the task: $$n^2=n^2-(2n-1)+(2n-1)=(n^2-2n+1)+2n-1=(n-1)^2+2n-1$$ So the original equation you ask about is correct.

Answer 4

It seems you have a hint in the wording of the problem itself: "if follows by the principle of mathematical induction that f(n) is bound from above by a constant times n for all n>=1"

this statement is true BUT it actually means that there is no constant c you can choose for which for all big enough n the equation will hold. Remember that you first pick a constant and then test for all sufficiently large n. ∃c>0 , ∀n≥n0 and not the other way around

To clarify as Brassard intented it in Fundamentals of Algorithms (from which this question comes): You get that f(n)<(c+2)*n BUT f(n)=n^2 so => n^2<(c+2)*n

now divide both sides by n and you get n < c+2 and that cant be because c is a constant and n has no limitations on how large it is. First you select the c and then it has to apply to all n you might try.