What is the Big O complexity of this equation?

Question

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

Answer 1

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.

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