Suppose you have a partition p of n into atmost k parts, say $$\{i_1, i_2, ..., i_j, ..., i_{k-1}\}$$ For example $\{1, 4\}$ is a partition of 10 into 3 parts (in this notation i am specifying the partition points, not the part lengths, i.e {1} , {2,3,4}, {5,6,7,8,9,10} are the three partitions)

Consider $$I(n, k) = min_p \sum_j {\frac {(i_{j+1} - i_j)} {2^{j}}}$$

Can we say anything meaningful about a lower bound on $I(n, k)$? I am specifically interested in the question when k is a function of n that grows slowly, like $log \ n$, or slower than $n^{1/{\epsilon}}$ for any ${\epsilon} > 0$.

I'm actually not sure if anything meaningful can be said here, so any ideas on how to approach this question would be very welcome

Any pointers to literature in this regard or a counter example showing no meaningful bound exists will be great. Intuitively, it seems like if i pick a partition of size $log \ n$ for example, no matter how i choose such a partition I cannot have $I(n, k) = O(1)$ for example. So I would probably guess $I(n,O(log\ n)) = O(log \ n)$.