0
$\begingroup$

Given $H(x) = lg(f(n))$, where $f(n)$ is an asymptotically positive function, is it always true that if $f(n) = \Theta(g(n))$, then

$H(x) = lg(\Theta(g(n)))$

$\Rightarrow H(x) = \Theta(lg(g(n)))$

To illustrate, Is $lg(n + c) = \Theta(lg(n))$ provided that $c > 0$ and $c$ is a big number?

  • 0
    Please use `\log` or `\ln`.2012-03-18

1 Answers 1

1

What is true is that if $f(n) = \Theta(g(n))$ with $f, g > 0$ then $\log f(n) = \log g(n) + O(1)$. If in addition either $g(n) \to \infty$ or $g(n) \to 0$ as $n \to \infty$, then $\log f(n) = \Theta(\log g(n))$.