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, 2021 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, 2021 at 11:58
  • $\begingroup$ Sorry, I am unable to find "3.2.8" - is it correct/exact numbering? $\endgroup$
    – zkutch
    Aug 1, 2021 at 12:03
  • $\begingroup$ It is 3.2-8. Sorry. On page 60. $\endgroup$
    – Emad
    Aug 1, 2021 at 12:04
  • $\begingroup$ It is the last exercise before the problems. $\endgroup$
    – Emad
    Aug 1, 2021 at 12:05

1 Answer 1

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, 2021 at 12:08
  • $\begingroup$ I don't possess a copy of CLRS, unfortunately. $\endgroup$ Aug 3, 2021 at 15:42
  • $\begingroup$ The problem says: Show that $kln(k) = \Theta(n)$ implies $k = \Theta(\frac{n}{ln(n)})$ $\endgroup$
    – Emad
    Aug 3, 2021 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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