# Finding a $g(n)$ so that $f(n) = O(g(n))$

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:

1. Can $$c$$ be dependent on $$n$$? By definition it seems like the answer is no since $$c$$ is a constant.

2. 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!

• See Faulhaber's formula You will need to increase the exponent that you were trying by $1$. – plop Feb 4 at 22:41

Suppose that you don't really know Faulhaber's formula.

Let's prove by induction that $$S_k(n)=\sum_{t=1}^n t^k\in O(n^{k+1})$$

For $$k=0$$ we have that $$S_0(n)=n\in O(n)$$.

Assume that for all $$s we have that $$S_s(n)\in O(n^{s+1})$$.

In order to bound $$S_k(n)$$, lets start with computing the difference $$S_{k+1}(n+1)-S_{k+1}(n)$$ in two ways. Yes, the subscript is overshooting. It is $$k+1$$ rather than $$k$$.

\begin{align} (n+1)^{k+1}&=S_{k+1}(n+1)-S_{k+1}(n)\\ &=\sum_{t=1}^{n+1}t^{k+1}-\sum_{t=1}^{n}t^{k+1}\\ &=1+\sum_{t=1}^{n}(t+1)^{k+1}-\sum_{t=1}^{n}t^{k+1}\\ &=1+\sum_{t=1}^{n}\left[(t+1)^{k+1}-t^{k+1}\right]\\ &=1+\sum_{t=1}^{n}\sum_{s=0}^{\color{red}{k}}\binom{k+1}{s}t^s\\ &=1+(k+1)\color{red}{\sum_{t=1}^{n}t^k}+\sum_{s=0}^{k-1}\binom{k+1}{s}\sum_{t=1}^{n}t^s\\ &=1+(k+1)\color{red}{S_k(n)}++\sum_{s=0}^{k-1}\binom{k+1}{s}S_s(n) \end{align}

Solving in the equation above for the term in red, $$\color{red}{S_k(n)}$$, we get that it is equal to $$\frac{1}{k+1}(n+1)^{k+1}$$ plus a linear combination of $$S_s(n)$$ for $$s. Since these are in $$O(n^k)$$, it follows that $$S_k(n)\in O(n^{k+1})$$.

In your case $$f(n)=n^5S_{22}(n)\in n^5O(n^{23})=O(n^{28})$$

For any $$f$$ we have $$f \in O(f)$$ i.e. trivial answer to your question is $$g=f$$. Presumably you need to clarify more exactly conditions on $$g$$. On other hand if we change all members of sum with maximum one, then we have $$f \in O(n^{28})$$.

1. $$c$$ is independent from $$n$$ by definition
2. outgoing from 1. you cannot consider $$c = (n-1)n^{5}$$
A simple way to estimate/bound $$\sum_{0 \le k \le n} k^m$$ is to approximate by an integral (do a sketch of the curve and the staircase representing the sum), so you see:
\begin{align*} \sum_{0 \le k \le n} k^m \le \int_0^n x^m \, \mathrm{d} x \\ = \frac{n^{m + 1}}{m + 1} \end{align*}