0
$\begingroup$

For example:

$f(n) = n(log_2 n)^4$ vs $g(n) = n^{1/3}$

Does f(n) grow slower than g(n) as a general rule, even for decimal exponents? I tried doing a limit test but symbolab limit calculator is saying that Steps are currently not supported for this problem.

I graphed them over a large range and it does appear that g(n) grows asymptotically faster.

$\endgroup$
1
$\begingroup$

I think you may be confused about the definition of Big O - graphing f(n) and g(n) shows f(n) surpassing g(n) at nearly every scale.

O(f(n)) > O(g(n) because g(n) is a fractional power polynomial, which is by definition sublinear (if you linearly plug numbers into a square root, cube root, etc., the rate at which the output increases decreases with each successive computation). g(n) is a "n log star n" polynomial meaning it follows the form of a log to a power multiplied by n. The rate of growth of these types of functions far exceeds fractional polynomials and its not hard to see why - n is a term of the function, so we know its at least linear.

Here's a helpful resource: https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.