I have the following homework problem, with given solution but I do not understand why certain choices in the solution were made as opposed to my own (incorrect) solution and I would like some clarification.

The question is to compare the growth rates of several functions using o, O and $\Theta$. It is the first time I have seen this notation and it is assumed knowledge for the class.

I am given the relation:

$f(n) \leq c.g(n) \Leftrightarrow \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$.

I have the following function $n\log n$. I am then supposed to compute o$(n \log n)$, according to the solution. As I interpreted the relation above and in the problem I had picked $f(n)$ and $g(n)$ to be the same $n \log n$ and evaluated to find that limit and quickly concluded my answer was incorrect.

The solution sets $f(n)=n^l$, where $l \in \mathbb{N}$ and $g(n)=2^n$ and the proceeds to calculate the limit and shows that it is in fact 0 as $n \rightarrow \infty$. I am fine with calculating the limit, I do not get why $f$ and $g$ were set to be what they were and how I would make this choice in the future, for say a different function not $n \log n$.

Any help in explaining why it has to be this way, would be really appreciated. Thanks!

  • 3
    $\begingroup$ "I have the following function $o(n\log n)$." I don't understand what you're trying to say. That's like saying "I have the following number $<7$." $o$ is a relationship between two functions. $\endgroup$ – David Richerby Nov 3 '16 at 8:44
  • $\begingroup$ The assumption that you made is not valid. Having $f(n) \leq c \cdot g(n)$, you cannot say that the limit is zero. Also, it is clear that $f(n)=n^l$ (for constant $l$) is polynomial, while $g(n)=2^n$ is exponential. Exponential $g(n)$ is obviously growing much faster than polynomial $f(n)$, that's why $f(n) \in o(g(n))$. $\endgroup$ – orezvani Nov 3 '16 at 12:02
  • $\begingroup$ @DavidRicherby, sorry that is bad wording on my part. I mean to say, I was given the following $n \log n$, and I am supposed to use the little o notation o$(n \log n)$ to show that the limit of $\frac{f(n)}{g(n)}\rightarrow 0 $ as $n \rightarrow \infty$ $\endgroup$ – Aesir Nov 4 '16 at 7:41
  • $\begingroup$ @emab, perhaps it is my fault in how I have asked the question, but you haven't understood my problem at all. I am in full agreement with what you have said. My question is, given the relation I gave above, and $n \log n$ and told to find o$(n \log n)$, why does the solution proceed to calculate $\lim_{n \rightarrow \infty} \frac{2^l}{2^n}$? How do they pick $f(n) = n^l$ and $g(n)=2^n$, when they just give, $n \log n$ and the relation I stated in my question. Does that help make it any clearer? $\endgroup$ – Aesir Nov 4 '16 at 7:47
  • 1
    $\begingroup$ @DavidRicherby Thanks, I will do that then, because I can't make sense of it either, and I thought perhaps it I just because this is a new topic for me, that maybe there was some prior knowledge that I didn't have. $\endgroup$ – Aesir Nov 4 '16 at 11:57

Your Answer

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

Browse other questions tagged or ask your own question.