Algorithm analyse with Big-Theta notation

Question

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?

Answer 1

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

Answer 2

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.