# Meaning of this two-variable asymptotic notation

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)$$?

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

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 there exist constants $$0 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 there exist constants $$0 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.

• 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?
• The problem says: Show that $kln(k) = \Theta(n)$ implies $k = \Theta(\frac{n}{ln(n)})$