2
$\begingroup$

I saw this question Can I simplify log(n+1) before showing that it is in O(log n)? and wanted to know if a similar situation was also true.

Namely, is $\log(n-1) \in \Omega(\log(n))$?

$\endgroup$
2
$\begingroup$

Having $n-1 \gt \sqrt{n}$, when $n \gt 3$ we can write $$\log (n-1) \gt \log \sqrt{n} = \frac{1}{2}\log n$$ So, taking $N=3$ and $C=\frac{1}{2}\gt 0$ we fulfilled definition for $\Omega$.

$\endgroup$
1
  • $\begingroup$ Thank you! @zkutch $\endgroup$
    – imconfused
    Feb 25 at 6:59
2
$\begingroup$

As you have seen, $\log(n+1) \in \mathcal{O}(\log n)$. That means that $\log n \in \Omega(\log( n + 1))$. Now you can change $n$ with $n-1$ and have your answer.

To be more precise, $\log(\alpha n^{\beta} + \gamma) \in \Theta(\log n)$ for any $\alpha, \beta, \gamma \in \mathbb{R}_{>0}$.

$\endgroup$
3
  • $\begingroup$ Hope Your $\mathbb{R}_+^*$ doesn't contain $\alpha=0$, as then we have constant on left side. $\endgroup$
    – zkutch
    Feb 24 at 10:47
  • $\begingroup$ Sorry, I am using French notations, as explained in en.wikipedia.org/wiki/Real_number#Vocabulary_and_notation It indeed means "any positive real number not zero". I modified my answer, I hope it is clearer now. $\endgroup$
    – Nathaniel
    Feb 24 at 10:50
  • $\begingroup$ Thank you! @Nathaniel $\endgroup$
    – imconfused
    Feb 25 at 6:58

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.