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

Question

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!

Answer 1

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<k$ 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<k$. 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})$

Answer 2

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

Now about questions:

1. $c$ is independent from $n$ by definition
2. outgoing from 1. you cannot consider $c = (n-1)n^{5}$

Answer 3

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

By sandwiching the staircase between curves (start/end of each staircase step), you get lower and upper bounds.