1
$\begingroup$

What does $k \ln(k) = \Theta(n)$ mean? Does it mean that $k$ is a function of $n$ and we actually had better write $k(n)\ln(k(n)) = \Theta(n)$?

$\endgroup$
5
  • 1
    $\begingroup$ If $k$ and $n$ are independent, then we have constant belongs to $\Theta$, which, of course is true, but is it what you want? Otherwise, with $k(n)$ or $n(k)$, everything depends on these functions. $\endgroup$
    – zkutch
    Aug 1 at 11:55
  • $\begingroup$ @zkutch It is part of an exercise of CLRS so I was wondering what it means. Exercise 3.2.8. It looks like it should be a function rather than a constant. $\endgroup$
    – Emad
    Aug 1 at 11:58
  • $\begingroup$ Sorry, I am unable to find "3.2.8" - is it correct/exact numbering? $\endgroup$
    – zkutch
    Aug 1 at 12:03
  • $\begingroup$ It is 3.2-8. Sorry. On page 60. $\endgroup$
    – Emad
    Aug 1 at 12:04
  • $\begingroup$ It is the last exercise before the problems. $\endgroup$
    – Emad
    Aug 1 at 12:05
2
$\begingroup$

It roughly means "for any two constants $0 < c < C$, the following holds whenever $k,n \in \mathbb{N}$ and $cn \leq k \ln k \leq Cn$".

For example, consider the claim "if $k = \Theta(n)$ then $(1+1/n)^k = \Theta(1)$". This means "for any two constants $0 < c < C$ there exist constants $0 < m < M$ such that following holds whenever $k,n \in \mathbb{N}$ and $cn \leq k \leq Cn$: $m \leq (1+1/n)^k \leq M$".

The assumptions on the domain of $k,n$ are usually clear from context, but do create an ambiguity, which is why the interpretation above is only rough.


Problem 3.2-8 from CLRS is as follows:

Show that $k\ln k = \Theta(n)$ implies $k = \Theta\left(\frac{n}{\ln n}\right)$.

We can expand this as follows:

For any two constants $0<c<C$ there exist constants $0<m<M$ such that the following holds: if $k,n \in \mathbb{N}$ satisfy $cn \leq k\ln k \leq Cn$ then $m\frac{n}{\ln n} \leq k \leq \frac{n}{\ln n}$.

However, this is certainly not the intended interpretation, since $\ln 1 = 0$, and so we get a division by zero! Instead, I propose the following interpretation:

For any two constants $0<c<C$ there exist constants $0<m<M$ and $N>0$ such that the following holds: if $k,n \geq N$ satisfy $cn \leq k\ln k \leq Cn$ then $m\frac{n}{\ln n} \leq k \leq M\frac{n}{\ln n}$.

This is in the spirit of the usual definition of big O.

The idea of the proof is that since $k\ln k = \Theta(n)$, we have $\ln k = \Theta(\ln n)$. Showing this requires some arithmetic.

$\endgroup$
3
  • $\begingroup$ So I tried to introduce some $m$ and $M$ for problem 3.2-8 but I failed. Can you give me some hint on that? $\endgroup$
    – Emad
    Aug 3 at 12:08
  • $\begingroup$ I don't possess a copy of CLRS, unfortunately. $\endgroup$ Aug 3 at 15:42
  • $\begingroup$ The problem says: Show that $kln(k) = \Theta(n)$ implies $k = \Theta(\frac{n}{ln(n)})$ $\endgroup$
    – Emad
    Aug 3 at 16:01

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.