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}$$



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.
