I am having some difficulty in thinking about asymptotic notation and the use of the $=$ symbol when manipulating equations involving asymptotic notation.
(This is the definition that I am dealing with here. $f(n)∈Θ(g(n))$ means that there exist constants $k_1$ and $k_2$ such that for all $n$ larger than some $n_0$, we have, $ k_1g(n)≤f(n)≤k_2g(n) $.)
So for example can this equation:
$$ \sum_{i=1}^{n}f_i(x)\Theta(g(n)) $$
be written to be 'equal' to:
$$ \Theta(g(n))\sum_{i=1}^{n}f_i(x) $$
And if so, why? Is there a proof involving the definition of the big-theta notation that shows that:
$$ \sum_{i=1}^{n}f_i(x)\Theta(g(n)) = \Theta(g(n))\sum_{i=1}^{n}f_i(x)$$
Because from what I can tell, the presence of the $\Theta(g(n))$ could be any old function that is bounded above by a constant factor times $g(n)$ and bounded below by some constant factor times $g(n)$. So why is it trivial to just factorize the $\Theta(g(n))$ out of the summation?
Also, when we have two equations which contain asymptotic notation in them, what does it mean to have them be 'equal' to each other? So, for the example above, what would it mean?
Thanks!
Best Answer
By your quoted definition, there exist positive constants $k_1$ and $k_2$ such that $k_1g(n)\leq f(n)\leq k_2g(n)$ if $f(n)=\Theta(g(n))$. Then for each term in the sum, let's denote the $\Theta(g(n))$ term by $g_i(n)$ where $k_ig(n)\leq g_i(n)\leq m_ig(n)$ for some positive constants $k_i$ and $m_i$. Then we have $$\sum_{i=1}^nf_i(x)\,k_i\,g(n)\leq\sum_{i=1}^nf_i(x)\,g_i(n)\leq\sum_{i=1}^nf_i(x)\,m_i\,g(n)$$ This expression will still hold if we make the left side smaller and the right side larger. Letting $$k=\min_{1\leq i\leq n}k_i\text{ and }m=\max_{1\leq i\leq n}m_i$$ we get $$\sum_{i=1}^nf_i(x)\,k\,g(n)\leq\sum_{i=1}^nf_i(x)\,g_i(n)\leq\sum_{i=1}^nf_i(x)\,m\,g(n)$$ Since $k\,g(n)$ and $m\,g(n)$ do not depend on $i$, we can factor them out of the sums to get $$k\,g(n)\sum_{i=1}^nf_i(x)\leq\sum_{i=1}^nf_i(x)\,g_i(n)\leq m\,g(n)\sum_{i=1}^nf_i(x)$$ Then with $g_i(n)=\Theta(g(n))$, we have found two positive constants $k$ and $m$ so that $$k\,g(n)\sum_{i=1}^nf_i(x)\leq\sum_{i=1}^nf_i(x)\,g_i(n)\leq m\,g(n)\sum_{i=1}^nf_i(x)$$ This shows that $$\sum_{i=1}^nf_i(x)\,g_i(n)=\Theta(g(n))\sum_{i=1}^nf_i(x)$$ and hence that $$\sum_{i=1}^nf_i(x)\,\Theta(g(n))=\Theta(g(n))\sum_{i=1}^nf_i(x)$$