1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    May 10, 2021 at 20:38

3 Answers 3

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ tank you sir .. $\endgroup$
    – askMe
    May 10, 2021 at 20:11
1
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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! $$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.