5
$\begingroup$

Can I take $\log$ on both sides of the following inequality
$$f(n) \leq cn^k$$ and get $$\log (f(n)) \leq kc\log n$$ I know that by rules the result inequality should be like this $$\log(f(n)) \leq \log(cn^k)$$ but I read in book where inequality (1) $\to$ in inequality (2) and want to know which way it was done

Edit: this is not general case, the questions relates to the algorithms and O-notation

$\endgroup$
  • 2
    $\begingroup$ Semantic nitpicking, but "add log" is not the best way to put it. "Add" generally refers to te operation of addition, and what you have here is more commonly referred to as "taking logs". $\endgroup$ – fkraiem Jan 29 '14 at 18:08
4
$\begingroup$

yes you can since $log$ is an increasing function and hence preserves the inequality. the main condition is that both sides lies in the domain of $log$ i.e. they are positive
$$\log(f(n)) \leq \log [cn^k]=\log c+\log n^k=\log c+k\log n $$ If $c >1$ then $\log c>0$ and so $$\log(f(n)) \leq k\log n\leq kc\log n $$

$\endgroup$
  • 1
    $\begingroup$ However, $\log(cn^k)\ne kc\log n$ in general. $\endgroup$ – Henning Makholm Jan 29 '14 at 17:31
  • $\begingroup$ @HenningMakholm yes, sure you are right $\endgroup$ – Semsem Jan 29 '14 at 17:32
  • $\begingroup$ So if this formula applies to algorithms then reform from (1) to (2) inequality is correct? Because k and c are constants and have no significant impact on inequality in general. $\endgroup$ – Raf Jan 29 '14 at 17:44
  • $\begingroup$ I will your question now, I complete my answer $\endgroup$ – Semsem Jan 29 '14 at 17:46
  • $\begingroup$ @Raf: Um, just because they are constants doesn't mean they "have no significant impact on the inequality". Are you implicitly trying to asymptotic analysis without telling anyone that's what you're doing? $\endgroup$ – Henning Makholm Jan 29 '14 at 17:57
7
$\begingroup$

You can take the logarithm on both sides of the inequality, if you know the numbers are positive. This produces $\log(f(n))\le \log(cn^k)$.

However $\log(cn^k)$ is not the same thing as $kc\log n$, so your second inequality doesn't follow. What you do have is $\log(cn^k) = \log(c) + k\log(n)$, so you can get $$ \log(f(n)) \le \log(c) + k\log(n)$$

$\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.