Final answer:
To demonstrate that f(n) is O(g(n)), we find constants c and n0 such that f(n) <= c*g(n) for all n >= n0. It is shown using properties of logarithms and polynomials that 4nlogn + n is eventually outgrown by a suitable multiple of (n^2 - n)/2 for sufficiently large n, proving f(n) = O(g(n)).
Step-by-step explanation:
To show that f(n) = O(g(n)), we need to find positive constants c and n0 such that f(n) ≤ cg(n) for all n ≥ n0. We have f(n) = 4nlogn + n and g(n) = (n2 − n)/2. We want to find a constant c such that 4nlogn + n ≤ c(n2 − n)/2 when n is sufficiently large.
From logarithm properties, we know that logn increases slower than any polynomial. So there exists a constant c such that 4nlogn ≤ c(n2 − n)/4 for all n ≥ n0, as the term n2−n will eventually outgrow 4nlogn. Additionally, n is clearly less than (n2 − n)/4 for n ≥ 2. Hence, adding the two conditions we get 4nlogn + n ≤ c(n2 − n)/2 for some c and all n ≥ n0, demonstrating that f(n) = O(g(n)).