Final answer:
For the function f(n) = 3n² - 5n + 4, a suitable function g(n) is n². Proving that f(n) ∈ θ(n²) involves showing that f(n) is bounded above by a constant multiple of n² and also bounded below by a different constant multiple of n² for sufficiently large n.
Step-by-step explanation:
When looking at the function f(n) = 3n² - 5n + 4, we want to find a function g(n) such that f(n) ∈ θ(g(n)). To prove this relationship, we can use the definitions of Big O, Theta, and Omega, or alternatively the limit test. In this scenario, a good choice for g(n) would be g(n) = n², since the dominant term in f(n) is 3n², and the lower-order terms (-5n and +4) become negligible as n grows large.
To prove that f(n) ∈ θ(n²), we need to show both f(n) ∈ O(n²) and f(n) ∈ Ω(n²). For the O(n²) part, we must find positive constants c1 and n0 such that 0 ≤ f(n) ≤ c1 · n² for all n ≥ n0. We can choose c1 = 3 and n0 = 1 to satisfy this condition since the quadratic term will always be larger than the linear term and constant term for n ≥ 1.
For the Ω(n²) part, we need to find positive constants c2 and n0 such that 0 ≤ c2 · n² ≤ f(n) for all n ≥ n0. We can choose c2 = 2 and the same n0 = 1, as even with the subtraction of the linear term and constant term, the function f(n) will always be bounded below by a multiple of n² for all n ≥ 1.
Therefore, we can conclude that f(n) ∈ θ(n²).