# A Question Regarding Asymptotic Notations

$g(n) = \Theta(n^2)$, $f(n) = g(n) + g(n-1) + ... + g(2) + f(1)$

Given the conditions above, is it suitable for me to conclude that $f(n) = \Theta(ng(n))$?

As the number of the $g(n)$ terms in $f(n)$ seems to grow with $n$... .

$g(n)$ and $f(n)$ are asymptotically positive functions.

• How is the Big Theta notation defined? If you answer this question, the answer to your HW problem is not too hard either. Oct 13, 2014 at 19:05
• Well, I know that $g(n)$ is bounded by two $n^2$s multiplied by some constants, but I don't really see how that gets me anywhere... .
– user182048
Oct 13, 2014 at 19:24
• Note that this is true only because of the specific conditions on $g(n)$. If e.g. $g(n) \in \Theta(\frac1n)$ then the conclusion doesn't hold. Feb 1, 2018 at 23:08

$g$ is bounded above and below asymptotically, i.e., there exist constants $c, C$ and there exists $N \in \mathbb{N}$ such that $$cn^2 \leq g(n) \leq Cn^2$$ for all $n \geq N$.
In what follows I assume that you meant $g(1)$ instead of $f(1)$ in your question. We almost have the following inequalities: $$c \cdot 1^2 + \ldots + c \cdot n^2 \leq f(n) = g(1) + \ldots + g(n) \leq C \cdot 1^2 + \ldots + C \cdot n^2.$$ "Almost" in the sense that this is only true up to a constant tail end (for the numbers from $1$ to $N$).