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