0
$\begingroup$

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

$\endgroup$
3
  • 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

1
$\begingroup$

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

$\endgroup$

Your Answer

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