1
$\begingroup$

having problems with big oh and big omega functions when there is a $\log n$ added or subtracted. For example how do I deal with $n+\log n$ or $n-\log n$ when I have to determine whether the function is in $\Omega(n)$ or in $\Omega(n^2)$? For example, is $n-\log n$ in $\Omega(n)$ or in $\Omega(n^2)$?

I cannot ignore the log function and am not sure how to deal with it. Polynomials and logs when multiplied I find OK. But I have a mental block over this one so help would be appreciated

$\endgroup$

3 Answers 3

2
$\begingroup$

You are right that you cannot a priori ignore additional terms, although morally you can as the "smaller" terms do not contribute to the asymptotic growth.

As an example $f(n) :=n+\log n$ is in $\Theta(n)$. Why? Going back to the definition, we want to show that $f(n)$ is in $O(n)$ and in $\Omega(n)$. Showing $f(n)\in \Omega(n)$ is immediate, as $f(n) \geq n$ for all $n>0$.

To show that $f(n)$ is in $O(n)$, simply notice that for large enough $n$ (say $n>N$ for some constant $N$) we have $\log n \leq n$ and thus $f(n)\leq 2n$ for all $n>N$. By definition $f(n)\in O(n)$.

$\endgroup$
0
$\begingroup$

Actually, you CAN ignore the log function in a sum or substraction, because the log is always asymptotically negligible in front of $n^x$, for every $x > 0$.

If you consider the function $f(n) = n^x + \alpha\log n$ (where $x > 0$ and $\alpha \in \mathbb{R}$), then there exists $A, B \in \mathbb{R}_+^*$ such that $An^x \leq f(n) \leq Bn^x$. That means that $f\in \Omega(n^x)$ and $f\in \mathcal{O}(n^x)$.

$\endgroup$
2
  • $\begingroup$ Agreed with the f(n) =n^2 or cubed -logn as the polynomial grows faster we can ignore the log n. f(n) grows faster than log n. Is it sufficient then to just prove that f(n) =n and is in Big omega and ignore the log term on the basis that as Tassle says logn<n . is this sufficient for a formal proof $\endgroup$
    – david
    Feb 22, 2021 at 15:40
  • $\begingroup$ Sorry, I didn't really get your question… I'll try to answer what I understood. When you have a sum $f(n) = g(n) + h(n)$ with $h \in o(g)$ (see en.wikipedia.org/wiki/Big_O_notation#Little-o_notation), then $f\in \Omega(g)$ and $f\in \mathcal{O}(g)$. This is the case in your question, since $\log \in o(n^x)$ for $x > 0$, and yes it is sufficient for a proof. $\endgroup$
    – Nathaniel
    Feb 22, 2021 at 15:48
0
$\begingroup$

In your example, $n-\log(n)=\theta(n)$, that is $n-\log(n) = \Omega(n)$ and also $n-\log(n)=O(n)$.

You can see this like that:

  • $n-\log(n)\le n = O(n)$
  • $n-\log(n) \ge n - 0.5n = \Omega(n)$
$\endgroup$
6
  • $\begingroup$ as n-logn is always less than n the function can only be in Big Oh . It cannot be in Big omega as if I divide by n^2 to fiind c I get 1-logn > or equal to c. As n gets greater than 2 n-logn gets more negative and c is no longer a constant so it cannot be in Big Omega. Am I on the right track? $\endgroup$
    – david
    Feb 24, 2021 at 9:09
  • $\begingroup$ From a certain point $log(n)\le0.5n$. This means that $n-\log(n)$ will actually not be negative, but actually if you substitute the inequality you get $n-\log(n)\ge 0.5n$, which is $\Omega(n)$. However, you are correct that it is not $\Omega(n^2)$. $\endgroup$
    – nir shahar
    Feb 24, 2021 at 10:20
  • $\begingroup$ sorry. I meant n-logn is not in Big Omega (n) not Big Omega (n^2). My original question is to prove (n-logn) = Ω(n) true or false. I was trying to prove it false by contradiction. Hence my reasoning of c needing to be a positive constant for all n> no.I am not sure where you came up with the 0.5n either. I plotted the graphs and n-logn is always under f(n)= n when n>1 $\endgroup$
    – david
    Feb 24, 2021 at 10:41
  • $\begingroup$ As my answer showed, it is indeed always lower than $n$. But, in the same time, it is bigger than $0.5n$. Try to draw this graph as well $\endgroup$
    – nir shahar
    Feb 24, 2021 at 11:32
  • $\begingroup$ You are right and thank you for your help . In fact from what you have said I can prove that n-logn =big theta(n) . $\endgroup$
    – david
    Feb 24, 2021 at 12:07

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.