3
$\begingroup$

I have the following functions that I need to rank in increasing order of Big-O complexity:

$$(\log n)^3, 10\sqrt n, n\log n, n\sqrt n, n^4 + n^3, (2.1)^n \cdot n^2, 3^n, 2^n \cdot n^3, n! + n, n^n. $$

My current ranking is as follows:

$$(\log n)^3 < 10\sqrt n < n\log n < n\sqrt n < n^4 + n^3 < (2.1)^n \cdot n^2 < 2^n \cdot n^3 < 3^n < n! + n < n^n. $$

Is my ranking of the functions in increasing order of complexity correct?

$\endgroup$
  • $\begingroup$ This question would probably be much more useful to others if you focus on the specific comparison you're not sure about (even if this means splitting it into multiple questions if there are a few you're not sure about). That could probably also help with your overall understanding, as you may think things are in a certain order, but you're not sure why or you believe so for the wrong reason. Focusing on one comparison allows for an in-depth explanation of why one is bigger than the other. Also, if this is homework, can't you just hand it in to be marked and see if it's correct? $\endgroup$ – Bernhard Barker Oct 6 '20 at 18:05
  • $\begingroup$ cs.stackexchange.com/q/824/755 $\endgroup$ – D.W. Oct 6 '20 at 19:13
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Oct 6 '20 at 19:13
13
$\begingroup$

You have mistake in $(2.1)^n \cdot n^2<2^n \cdot n^3$, because it is equivalent $\left(\frac{2.1}{2}\right)^n<n$

$\endgroup$
  • $\begingroup$ So, the other way around? $\endgroup$ – Broadsword93 Oct 6 '20 at 11:16
  • 3
    $\begingroup$ Others are correct. $\endgroup$ – zkutch Oct 6 '20 at 11:23
  • $\begingroup$ So: $$(\log n)^3 < 10\sqrt n < n\log n < n\sqrt n < n^4 + n^3 < 2^n \cdot n^3 < (2.1)^n \cdot n^2 < 3^n < n! + n < n^n. $$ $\endgroup$ – Broadsword93 Oct 6 '20 at 11:38
  • 1
    $\begingroup$ Yes. It is correct. $\endgroup$ – zkutch Oct 6 '20 at 11:50
  • $\begingroup$ Welcome. You can express your gratitude in estimating answer, if you count it worth. $\endgroup$ – zkutch Oct 6 '20 at 12:34

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.