How is f(x) = 4x^2 - 5x + 3 is O(x^2) derived

Question

Here are the steps that are used to prove the above

|f(x)| = |4x^2 – 5x + 3|
<= |4x^2|+ |- 5x| + |3|
<= 4x^2 + 5x + 3, for all x > 0
<= 4x^2 + 5x^2 + 3x^2, for all x > 1
<= 12x^2, for all x > 1 

Hence we conclude that f(x) is O(x^2)

I referred this But it does not help

Can someone explain the above proof step by step?

1. Why the absolute value of f(x) is taken ?
2. Why and how were all the term replaced by x^2 term?

Answer 1

Preparations

We start by loosely stating the definition of a function or algorithm f being in O(g(n)):

If a function f is in O(g(n)), then c · g(n) is an upper bound on f(n), for some non-negative constant c such that f(n) ≤ c · g(n) holds, for sufficiently large n (i.e. , n ≥ n0 for some constant n0).

Hence, to show that f ∈ O(g(n)), we need to find a set of (non-negative) constants (c, n0) that fulfils

f(n) ≤ c · g(n), for all n ≥ n0,                                (+)

We note, however, that this set is not unique; the problem of finding the constants (c, n0) such that (+) holds is degenerate. In fact, if any such pair of constants exists, there will exist an infinite amount of different such pairs.

---

Analysis

For common convention, we'll analyse your example using variable name n rather than x.

f(n) = 4n^2 - 5n + 3                                            (++)

Now, for your example, we may assume, without loss of generality (since we're studying asymptotic complexity: function/algorithm behavior for "large" n) that n > n0 where n0 > 0. This would correspond to the analysis you've shown in your question analyzing absolute values of x. Anyway, given this assumption, the following holds:

f(n) = 4n^2 - 5n + 3 < 4n^2 + 3, for all n > n0

Now let, again without loss of generality, n0 equal 2 (we could choose any value, but lets choose 2 here). For n0 = 2, naturally n^2 > 3 holds for n > n0, which means the following holds:

f(n) = 4n^2 - 5n + 3 < 4n^2 + 3 < 4n^2 + n^2, for all n > n0 = 2
f(n) < 5n^2, for all n > n0 = 2

Now choose c = 5 and let g(n) = n^2:

f(n) < c · g(n), for all n > n0,
                 with c = 5, n0 = 2, g(n) = n^2

Hence, from (+), we've shown that f as defined in (++) is in O(g(n)) = O(n^2).