runtime complexity

Question

i want to Order these runtime complexitys ascending. I tried to transform this and made a first try in ordering them which you can find behind the -->

$log4711$ --> 1.
$log^4(n)$ --> 2.
$log(n^4)$ --> $4log(n)$ --> 3.
$\sqrt[4]{n}$ --> $n^{\frac{1}{4}}$ --> 4.
$n^{\frac{3}{2}}$ --> 5.
$9^{log_3(n)}$ --> $n^2$ --> 6.
$e^{\frac{1}{3}n}$ --> 7.
$(n-1)!$ --> 8.

I am not sure if my solution is correct and how to transform $log^4(n)$

Best Regards

Looks pretty good, but if $\log^4n$ means $(\log n)^4$ then it exceeds $4\log n$. — Gerry Myerson, Mar 13 '23 at 09:24
Reordered the list to your numeration, so to check order we don't have to iterate through it for every line. — mihaild, Mar 13 '23 at 09:25

score 0 · Accepted Answer · answered Mar 13 '23 at 09:27

0

As $\log n$ growth infinitely, $\log^4n$ growth faster than $\log n$, and so lines $2$ and $3$ should be swapped.

If you know that $\log n$ growth slower than any power, than to compare $\log^4$ and $\sqrt[4]n$ you can say that $\log n$ growth slower than $\sqrt[16]n$, and then take $4$th power of both sides.

answered Mar 13 '23 at 09:27

mihaild

15,368

Thanks, I was unsure what $log^4(n)$ meant. I think like Gerry Myerson commented it does mean $(log n)^4$. – Dirk Vorgerb Mar 13 '23 at 09:35

runtime complexity

1 Answers1