By definition, we know that:
For $\sum_{i=1}^n 3^i\log_2(i) $ to be in order of $3^n\log_2(n)$ there needs to exists positive constants $C_1$ and $C_2$ such that:
- $C_1 |3^n\log_2(n)| \le |\sum_{i=1}^n 3^i\log_2(i)| \le C_2|3^n\log_2(n)|$
Omega is pretty much given as if we take 1 as a constant we automatically can see the inequality. Proof would be to substract $3^n\log_2(n)$ from both sides and, thus, we would end up with $0 \le \sum_{i=1}^{n-1} 3^i\log_2(i)$ which is true.
The Big-Oh proof is the tricky one for me. Are we allowed to use a constant that includes $n$ ? It's a question of juggling with the known inequalities and thus isolating out a constant. Not sure which way to look at it.
My question: What value can we use as $C_2$ to validate the Big-Oh definition for the inequality?
Thank you for the help.