1
$\begingroup$

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!

  • 2
    If $n$ is constant, then what is the sum varying with/against exactly? If $n$ is not constant, then how is the partition fixed? Otherwise, if there are an infinity of partitions, then is the set $A$ infinite? I assume $f,g$ are functions of sets; does $f\in O(g)$ mean that there exists a $C$ and a set $S$ such that $f(A)\le Cg(A)$ for all $A$ containing $S$ (i.e. $A\le S$ with respect to the containment partial order); or else is $f$ a function of the elements of some big set and we attach a special meaning to $f(A_i)$ for $A_i$ sets? I am failing to make sense of this at the moment.2012-12-14

0 Answers 0