Can't define growth rate order

Question

I have 2 functions, C(n) and A(n)

I do not know why A(n) is slower than C(n) because higher growth rate means slower runtime.

From my perspective, they both have root on numerator. However, A(n) is divided by logn, which means it should be less than root n. Thus whole A(n) becomes faster than C(n) since C(n) still has root n (even though it is n^1/3 but still has root) and is not divided by anything.

Is there very simplest way to define growth rate order?

Thank you very much if you can explain why A(n) is slower than C(n).

*"I do not know why A(n) is slower than C(n) because higher growth rate means slower runtime."* - Not necessarily. Suppose A(n) complexity is 1000000*n and B(n) complexity is n^3. A(n) is bounded, but it has a very large constant. [B(n) will outperform A(n) for n < 1000](https://www.symbolab.com/solver/equation-calculator/1000000n%20%3C%3D%20n%5E%7B3%7D). The takeaway is, if you know something about your dataset, you can select an asymptotically slower algorithm and still enjoy better performance in some cases. — jww, Jun 13 '17 at 21:52
I'm voting to close this question as off-topic because the underlying issue is about [math.se]. — Bernhard Barker, Jun 13 '17 at 23:11
Or perhaps it's just a duplicate of [What is a plain English explanation of “Big O” notation?](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) (Big O? Big Theta? Close enough). Or it's probably some combination of off-topic and a duplicate. — Bernhard Barker, Jun 13 '17 at 23:25

score 0 · Accepted Answer · answered Jun 14 '17 at 06:47

Both C(n) and A(n) have roots in the numerator, but they are different roots. In C(n) it is a cube root and in A(n) it is a square root. Another way to write them would be:

C(n) = Θ(n ^ (1/3))

and

A(n) = Θ(n ^ (1/2) / some-log-term)

Now it is clear that 1/3 < 1/2 and therefore with n large enough n^(1/3) is much less than n^(1/2) (and n^(1/2)/some-log-term too). In fact A(n) is arbitrarily larger which means C(n) << A(n)

Can't define growth rate order

1 Answers1