I am having trouble on the following algorithms question:
Given $f(n) = \sum^n_{y{=}1} (n^5\cdot y^{22})$, I am trying to find a $g(n)$ such that $f(n) = O(g(n))$. I know that this means I need to find constants $c,n_{0}$ so that $f(n) \leq g(n)$ for all $n > n_{0}$.
I began by considering the expansion of $f(n) = n^{5}\cdot1^{22} + n^{5}\cdot2^{22} + ... + n^{5}\cdot(n-1)^{22} + n^{5}\cdot n^{22}$.
This gave me two ideas for a solution:
First, I thought to set $g(n) = c \cdot n^{27}$ (given that this is the largest exponential term of $f(n)$), but where I am stuck is picking the right $c$. I had the idea of picking $(n-1)n^{5}$ (there are $n-1$ other terms and the largest exponential of each term is $n^{5}$), but I'm stuck for two reasons:
Can $c$ be dependent on $n$? By definition it seems like the answer is no since $c$ is a constant.
The choice of $c = (n-1)n^{5}$ is dubious. Consider the term $(n-1)^{22}n^{5}$, the largest portion is $(n-1)^{23}$, not $n^{5}$.
My second idea is to let $g(n) = c \cdot n^{5} + n^{27}$, and let $c = \sum^{n-1}_{y{=}1} (y^{22})$, but again this seems incorrect because $c$ depends on $n$.
I would love some feedback on these attempts, thanks!