Help showing that a function has order of n^2

127 Views Asked by At

Let $f:\mathbb{N}\rightarrow\mathbb{R}^+$ so that $f\in\Theta(n)$. Also, we define the function $g:\mathbb{N}\rightarrow\mathbb{R}^+$ as $$g(n)=\sum_{i=0}^{n}{f(i)}$$ Show that $g\in\Theta(n^2)$

$\Theta(n^2)$ and $\Theta(n)$ are in asymptotic notation.

I know that, by definition $(\exists c\in\mathbb{R}^+)(\exists n_{0}'\in\mathbb{N})$ so that $(\forall n\geq n_{0}')\ f(n)\leq c\cdot h(n)$ and $(\exists d\in\mathbb{R}^+)(\exists n_{0}''\in\mathbb{N})$ so that $(\forall n\geq n_{0}'`)\ d\cdot h(n)\leq f(n)$. This means that $f\in\Theta$.

If I add all of the $n$ amount of valuations of $f$ (from $0$ to $n$), because the worst and the best case of every one of them has the order of $n$, $g(n)$ is generated by $n$ times the order of $f$ (this is $n^2$).

I don`t know if this is the correct approach for the problem, ¿can someone help me identifying my mistakes and guide me into the proper solution?

1

There are 1 best solutions below

1
On BEST ANSWER

By hypothesis, there exist $k_1,k_2\in\mathbb{R}$, $N\in\mathbb{N}$ such that, for $n>N$, $k_1n<f(n)<k_2n$. Therefore, for $n>N$, $$\sum_{i=0}^{N-1}f(i)+\frac{k_1}{2}(n+N)(n-N+1)<\sum_{i=0}^n f(i)<\sum_{i=0}^{N-1}f(i)+\frac{k_2}{2}(n+N)(n-N+1).$$ But the left and right hand side are quadratic polynomials in $n$, which means that they can be asymptotically bounded below and above, respectively, by multiples of $n^2$. This is what it means for this function to be $\Theta(n^2)$, which is what we wanted to prove.