0
$\begingroup$

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!

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

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

$\endgroup$
2
$\begingroup$

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}$
$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.