0
$\begingroup$

I'm a trying to prove a recurrence relation (by substitution) for an algorithm class and I'm shamefully stuck in a rather simple looking inequality.

I need to solve this inequality for constant $c$:

$$\frac{3cn}{2} + \frac{n}{\log_{2}n} \ge cn$$

The problem is that I don't know how to deal with the logarithm!

Can anyone could point me in the right direction? Also, are there any good books or tutorials on this simple subject? I just returned to school and I can't remember simple things like this...!

$\endgroup$
2
$\begingroup$

The answer below the line shows the inequality is true, which I assumed is what you wanted as most algorithm problems come down to proving things not algebra. Re-reading your question shows you want to solve for $c$. Just ignore the $\log_2 n$ as anything special and just do the algebra to get $c$ by itself.

$\frac{3cn}{2}+\frac{n}{\log_2 n} \geq cn \iff \frac{n}{\log_2 n} \geq -\frac{1}{2}cn \iff \frac{-2}{\log_2 n} \leq c$


For $n>1$, $\log_2 n > 0$. So $\frac{n}{\log_2 n} > 0$. Hence $\frac{3cn}{2}+\frac{n}{\log_2 n} \geq cn$ since $\frac{3}{2}cn \geq 1cn$.

$\endgroup$
0
$\begingroup$

The LHS is not defined for $n \in (-\infty,0] \cup \{1\}$.

If $n>1$: $$c \geq 0 \geq -\log_n (4) = - \frac{\log_2 (4)}{\log_2 (n)} = \frac{-2}{\log_2 (n)} \iff \frac{n}{\log_2 (n)} \geq -\frac{nc}{2} \\ \iff \frac{3cn}{2} + \frac{n}{\log_{2}n} \ge cn $$

For $0<n<1$: as $n$ tends to $1$, $c \geq -\log_n (4)$ tends to $\infty$, so one does not want to go there.

$\endgroup$

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.