0
$\begingroup$

Is $(n \log n) + \frac{\lfloor (\log n)^2\rfloor + \log n}{2} = \Theta(n \log n)$ ?

My solution: $$ \begin{aligned} c_1 \cdot (n \log n) \le\,& (n \log n) + \frac{\lfloor(\log n)^2\rfloor + \log n}{2} \le c_2 \cdot (n \log n) &(\text{Divide by } n \log n)\\ c_1 \cdot 1 \le\,& 1 + \frac{1}{2} \cdot \left\lfloor \frac{\log n + 1}{n} \right\rfloor \le c_2 \cdot 1 \end{aligned} $$

I choosed $c_1 = 1$ so 1 is always $\le (1 + x + y )$ for $x,y \ge 0$ and $c_2 = 4 \ge ( 1 + x + y )$ for $0 < x,y < 1$.

So $(n \log n) + \frac{\lfloor(\log n)^2\rfloor + \log n}{2} = \Theta(n \log n)$.

Is my solution right?

$\endgroup$
  • $\begingroup$ Hi, I took the liberty of reformatting your question using LaTeX to make it more readable. Could you please check if my translation is corect? $\endgroup$ – Johannes Kloos Oct 17 '13 at 14:51
  • $\begingroup$ The result of the division is not correct, unless I misinterpreted the [x] notation. Note that in general, $\lfloor a \rfloor / b \neq \lfloor a/b \rfloor$. Also, I don't understand where the $x$ and $y$ are coming from - what exactly are you trying to say there? $\endgroup$ – Johannes Kloos Oct 17 '13 at 14:56
1
$\begingroup$

The solution is not correct, because it treats floor brackets as if they were parentheses.

General suggestion: deal with one inequality at a time. As follows:

Step 1 is to exhibit $c_1$ such that $$ c_1 n\log n\le (n \log n) + \frac{\lfloor (\log n)^2\rfloor + \log n}{2} \tag{1}$$ Clearly, $c_1=1$ works in (1).

Step 2 is to exhibit $c_2$ such that $$ (n \log n) + \frac{\lfloor (\log n)^2\rfloor + \log n}{2} \le c_2 n\log n \tag{2}$$ To this end, use the inequalities $\lfloor x \rfloor \le x$ and $\log n\le n$: $$ \frac{\lfloor (\log n)^2\rfloor + \log n}{2} \le \frac{ (\log n)^2 + \log n}{2} \le \frac{ n\log n + \log n}{2} \le n\log n $$ Hence, $c_2=2$ works in (2).

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

All you need is to show that $\frac{\lfloor (\log n)^2\rfloor + \log n}{2} = o(n \log n)$.

This is a special case of the general principle that if $g(n) = o(f(n))$ then $f(n) + g(n) = \Theta(f(n)) $. Try to prove this. Do not make the proof too hard.

| cite | improve this answer | |
$\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.