# Big Oh and Big Omega when $n$ and $\log n$ terms are in $f(n)$

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

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

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

• 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 Feb 22 '21 at 15:40
• 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. Feb 22 '21 at 15:48

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)$$
• 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? Feb 24 '21 at 9:09
• 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)$. Feb 24 '21 at 10:20
• 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 Feb 24 '21 at 10:41
• 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 Feb 24 '21 at 11:32
• 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) . Feb 24 '21 at 12:07