Question

Prove that 5n^2 − 2n + 16 is not O(n) using the definition of big-O. Note: This requires a proof by contradiction.

Answer 1

let's assume that 5n^2 − 2n + 16 = O(n)

f(n) = O(g(n)) means there are positive constants c and n0, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0

5n^2 − 2n + 16 = O(n)
=>  5n^2 − 2n + 16 <= c(n)
=>  5n^2+16 <= (c+2)n
=>  5n^2 <= (c+2)n
=>  5n <= (c+2)
=>  5n-2 <= c
for it to be true c must be >= 5n-2. so, c here is not a constant. since it depends on n.
hence this is proved wrong.

so, by proof of contradiction, 5n^2 − 2n + 16 is not O(n)