# 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.
Commented May 10, 2021 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 .. Commented May 10, 2021 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).$$

Since we know $$\log \frac{a}{b} = \log a - \log b % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaciiBaiaac+ % gacaGGNbWaaSaaaeaacaWGHbaabaGaamOyaaaacqGH9aqpciGGSbGa % ai4BaiaacEgacaWGHbGaeyOeI0IaciiBaiaac+gacaGGNbGaamOyaa % aa!43F0!$$ we can say: $$\frac{n}{{\log n}}.\log \frac{n}{{\log n}} = \frac{n}{{\log n}}(\log n - \log \log n) = n - \frac{{n.\log \log n}}{{\log n}} % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaSaaaeaaca % WGUbaabaGaciiBaiaac+gacaGGNbGaamOBaaaacaGGUaGaciiBaiaa % c+gacaGGNbWaaSaaaeaacaWGUbaabaGaciiBaiaac+gacaGGNbGaam % OBaaaacqGH9aqpdaWcaaqaaiaad6gaaeaaciGGSbGaai4BaiaacEga % caWGUbaaaiaacIcaciGGSbGaai4BaiaacEgacaWGUbGaeyOeI0Iaci % iBaiaac+gacaGGNbGaciiBaiaac+gacaGGNbGaamOBaiaacMcacqGH % 9aqpcaWGUbGaeyOeI0YaaSaaaeaacaWGUbGaaiOlaiGacYgacaGGVb % Gaai4zaiGacYgacaGGVbGaai4zaiaad6gaaeaaciGGSbGaai4Baiaa % cEgacaWGUbaaaaaa!644A!$$ on the other hand, we know clearly $$\log \log n < \log n % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaciiBaiaac+ % gacaGGNbGaciiBaiaac+gacaGGNbGaamOBaiabgYda8iGacYgacaGG % VbGaai4zaiaad6gaaaa!413D!$$ hence: $$\frac{{n.\log \log n}}{{\log n}} < \frac{{n.\log n}}{{\log n}} \to \frac{{n.\log \log n}}{{\log n}} < n \to \frac{{n.\log \log n}}{{\log n}} \in O\;(n) % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaSaaaeaaca % WGUbGaaiOlaiGacYgacaGGVbGaai4zaiGacYgacaGGVbGaai4zaiaa % d6gaaeaaciGGSbGaai4BaiaacEgacaWGUbaaaiabgYda8maalaaaba % GaamOBaiaac6caciGGSbGaai4BaiaacEgacaWGUbaabaGaciiBaiaa % c+gacaGGNbGaamOBaaaacqGHsgIRdaWcaaqaaiaad6gacaGGUaGaci % iBaiaac+gacaGGNbGaciiBaiaac+gacaGGNbGaamOBaaqaaiGacYga % caGGVbGaai4zaiaad6gaaaGaeyipaWJaamOBaiabgkziUoaalaaaba % GaamOBaiaac6caciGGSbGaai4BaiaacEgaciGGSbGaai4BaiaacEga % caWGUbaabaGaciiBaiaac+gacaGGNbGaamOBaaaacqGHiiIZcaWGpb % GaaGjbVlaacIcacaWGUbGaaiykaaaa!7045!$$ according to above explanation: $$T\;(n) = O\;(n) + n - O\;(n) \to T\;(n) \in O\;(n) % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamivaiaays % W7caGGOaGaamOBaiaacMcacqGH9aqpcaWGpbGaaGjbVlaacIcacaWG % UbGaaiykaiabgUcaRiaad6gacqGHsislcaWGpbGaaGjbVlaacIcaca % WGUbGaaiykaiabgkziUkaadsfacaaMe8Uaaiikaiaad6gacaGGPaGa % eyicI4Saam4taiaaysW7caGGOaGaamOBaiaacMcaaaa!5487!$$