# Algorithm analyse with Big-Theta notation

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?

• 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? – Johannes Kloos Oct 17 '13 at 14:51
• 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? – Johannes Kloos Oct 17 '13 at 14:56

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