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

  • 2
    $\begingroup$ How is the Big Theta notation defined? If you answer this question, the answer to your HW problem is not too hard either. $\endgroup$
    – eins6180
    Oct 13, 2014 at 19:05
  • $\begingroup$ 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... . $\endgroup$
    – user182048
    Oct 13, 2014 at 19:24
  • $\begingroup$ 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. $\endgroup$ Feb 1, 2018 at 23:08

1 Answer 1


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

The lefthand side and righthand side you need to simplify of course.


Your Answer

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