1
$\begingroup$

This question already has an answer here:

I have the following two functions

  • $f(n) = n\sqrt n + n \log n$
  • $\log_{100} n$

And I need to classify them into the followings:

  • $O(n)$, and/or
  • $O(n^2)$, and/or
  • $O(n^3)$, and/or
  • $O(n^{1.5})$, and/or
  • $\omega(n)$, and/or
  • $o(n\log n)$ (small o)
  • $\theta(n^{1.5})$,

Regarding the $\theta(n^{1.5})$, I am grasping it's idea newly, where do these functions set in. Also, does the function $f(n) =n^{0.9999}$ belong to $\theta(n^{1.5})$.

I would appreciate your feedback, as from your answers I am building up the knowledge for these.

$\endgroup$

marked as duplicate by David Richerby complexity-theory Oct 17 '18 at 19:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Am I supposed to define w(n) by myself? $\endgroup$ – Apass.Jack Oct 17 '18 at 18:22
  • $\begingroup$ it is possibly $\omega(n)$ $\endgroup$ – kelalaka Oct 17 '18 at 18:32
  • $\begingroup$ Welcome back to Computer Science! You can use LaTeX to typset mathematics, rather than doing it manually with sup tag and some other weird stuff. I edited to show you how; we also have a brief tutorial. $\endgroup$ – Apass.Jack Oct 17 '18 at 18:39
  • $\begingroup$ @kelalaka, thanks for the hint. tony9099, please edit if I have not updated your question correctly. $\endgroup$ – Apass.Jack Oct 17 '18 at 18:41
1
$\begingroup$
  • $\log_{100}n \in \mathcal{O}(log(n))$ since base change is a constant.
    • $\log n \in \mathcal{O}(n) $
    • $\log n \in \mathcal{O}(n^2) $
    • $\log n \in \mathcal{O}(n^3) $
    • $\log n \in \mathcal{O}(n^{3/2}) $
    • $\log n \not\in \mathcal{\omega}(n) $
    • $\log n \in \mathcal{o}(n \log n) $

This table gives the order;

First of all;

$$\lim_{n \rightarrow \infty} \frac{n \sqrt n}{n \log n} = \infty$$ by using this;

  • $f(n)= n\sqrt n + n\log n \in \mathcal{O}(n\sqrt n )$.
    • $ n\sqrt n \not\in \mathcal{O}(n)$
    • $n\sqrt n \in \mathcal{O}(n^2) $
    • $n\sqrt n \in \mathcal{O}(n^3) $
    • $n\sqrt n \in \mathcal{O}(n^{3/2}) $
    • $n\sqrt n \in \mathcal{\omega}(n) $
    • $n\sqrt n \not\in \mathcal{o}(n \log n) $,
$\endgroup$
  • $\begingroup$ Please remember that we're not a homework answering service. Answers that don't teach people how to solve the problem aren't very valuable at all. $\endgroup$ – David Richerby Oct 17 '18 at 19:51
  • $\begingroup$ Most questions of the for "Is this function big-O of this other function" can be flagged as duplicates of the one I marked. That question covers the general techniques and there's usually not much more to say, since the same functions tend to be used as examples each time. $\endgroup$ – David Richerby Oct 17 '18 at 20:13
  • $\begingroup$ @kelalaka Thanks a lot for your input :) I have edited the question and added a new bound as well as a new function. I would appreciate if you can have a look :) (PS: this is not a homework) $\endgroup$ – tony9099 Oct 18 '18 at 16:36
  • $\begingroup$ Take the limit at WolframAlpha. That easy. $\endgroup$ – kelalaka Oct 18 '18 at 16:39

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