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.

$\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 at 20:38
3
$\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.

$\endgroup$
1
  • $\begingroup$ tank you sir .. $\endgroup$ – askMe May 10 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).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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