f(n) = n log n, g(n) = n sqrt(n)/2
f(n) = (n^2-n)/2 , g(n) = 6n
using big-O definition finding c, n0?
i have tried with big-O notation: Let f f, the function to be estimated, be a real or complex valued function and let g g, the comparison function, be a real valued function. Let both functions be defined on some unbounded subset of the positive real numbers, and g ( x ) g(x) be strictly positive for all large enough values of x.
exist c,n0 so that f(x) <= c g(n) for all n >= n0, where c and n0 are positive constants(c is to find and is not unique).
For the first one for example:
just looking the functions, we see f(n) seems to be O(g(n)) because g(n) is polynomial. So I've tried to work on f(n): $$n log n \leq c \frac{n \sqrt n} {2} $$
$$ 2log n \leq c \sqrt n $$
$$ c \geq \frac{2 log n} {\sqrt n}$$ now my issue is find c and $n_0$