What is the Big O complexity of this equation? $$\frac{n+1}{2}(\log_2(n-1))+\frac{n+1}{2}-\log_2(1)-\log_2(3)-\dots-\log_2(n)$$
What is the Big O complexity of this equation?


My initial guess is $n \log(n)$
    But after a calculation, I found that it exhibits linear growth. 
    How do I prove this mathematically?


I do not need it to be too rigorous, as I am just beginning a course in CS. 


After some simplification, $$\log_2\left((n-1)^{\frac{n+1}{2}}\frac{1}{1}\frac{1}{3}\dots\frac{1}{n}\right) + \frac{n+1}{2}$$
    $$=\log_2\left((n-1)^{\frac{n+1}{2}}\frac{1}{1*3*\dots*n}\right) + \frac{n+1}{2}$$


 A: Hint. Assuming $n$ is odd, you can express the product with factorials:
$$
1*3*\dots*n = \frac{1*2*3*\dots*n}{2*4*\dots(n-1)} = \frac{n!}{2^{(n-1)/2} ((n-1)/2)!}
$$
Then use Stirling's approximation:
$$
\log_2(n!) = n \log_2(n) - n/\ln(2) + O(1)
$$
Then check if the $n \log n$ terms cancel each other out.
A: First, the first two terms are $\frac{n+1}{2}(\log_2(n-1))+\frac{n+1}{2}=\frac{n+1}{2}((\log_2(n-1))+1)\in O(n \log n)$  Then we have to prove the series at the end can't neutralize the growth.  We don't care about the base of logs, so I will use log to mean $\log_e$ The negative terms are $\log n!!$, where $n!!$ is the factorial function skipping alternate terms.We can use Stirling's approximation to say $$n!!\approx \frac {n!}{2^{\frac n2}(\frac n2)!}\approx\dfrac {\frac {n^n}{e^n}e^{\frac n2}}{2^{\frac n2}(\frac n2)^{\frac n2}}=\left(\frac ne\right )^{\frac n2}$$ so $\log n!! \approx \frac n2 (\log \frac ne)=\frac n2 (\log n-1)$  This would lead me (given the homework tag) to worry that all the $n \log n$ terms cancel and you are left with linear growth.  It is subtle.
