Consider a set $A$ that is partitioned into $n$ subsets $A_1 | A_2 | ... | A_n$ and a function $f \in \mathcal{O}(g)$.
Question: what is the tightest bound I can establish for $\sum_{i=1}^n f(A_i)$?
This is naively in $\mathcal{O}(A\cdot g(A))$, but it seems that since $\sum |A_i|=|A|$ and $\forall i, |A_i| \in \left[0..|A|\right]$, I should be able to establish a tighter $\mathcal{O}(g(A))$ bound. I am having trouble formalizing this argument.
As I am quite rusty with this, I'd appreciate someone pointing me in the right direction for a proof (or to tell me that I'm crazy). Thanks!