A Question Regarding Asymptotic Notations

475 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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