# Is $\frac{n}{\log n} \log \frac{n}{\log n} = O(n)$?

I have an algorithm with this time complexity:

$$T(n) = O(n) + \frac{n}{\log n} \cdot \log \frac{n}{\log n}.$$

I tried to figure out how to solve this and I tried to say something like this : if I have $$\frac{\log n}{n}$$ then the value is going to be very small, if I switch between them the value becomes very big, so I came to this: $$T(n) = O(n)+$$ something very big.

I am trying to determine if the result is larger than linear time or not, but I am lost.

• Don't use images for important content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. – D.W. May 10 at 20:38

Clearly, $$\log(\frac{n}{\log(n)}) \le \log(n)$$.

Substitute this into the equation to get that $$T=O(n)+\frac{n}{\log(n)}\left(\log\left(\frac{n}{\log(n)}\right)\right)\le O(n)+\frac{n}{\log(n)} \log(n)=O(n)+n=O(n)$$

So $$T=O(n)$$, and indeed it is not bigger than linear time.

• tank you sir .. – askMe May 10 at 20:11

From the definition of big-O: $$f(n)=\mathcal{O}(n)$$ if there exists a positive constant real number $$c$$ that $$f(n)\leq cn.$$ I claim that $$\frac{n}{\log n} \log \frac{n}{\log n} = \mathcal{O}(n)$$ So, for proving it we act as follow $$\frac{n}{\log n} \log \frac{n}{\log n} \leq cn$$ multiply each side of inequality by $${\log n}$$: $$n \log \frac{n}{\log n} \leq cn\log n$$ on the other hand we know that as $$n\to \infty$$ $$\log \frac{n}{\log n}\leq \log n$$

$$\rightarrow\forall c\geq 1\hspace{10pt} n \log n \leq cn\log n. \square$$

So $$\frac{n}{\log n} \log \frac{n}{\log n} = \mathcal{O}(n).$$