For: $$\sum^{k}_{i=1} \log(x_i)$$ where: $$\sum^{k}_{i=1} x_i = n$$ Is there any big-$O$ result in terms of $n$ ?

I found this, but is not what I'm looking for.

New contributor
Dani Mesejo is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

It is easy to show that $\prod_{i = 1}^{n}x_i$ is maximized when all $x_i$'s are equal, i.e., $x_i = n/k$ for every $i \in \{1,\dotsc,k\}$.

Therefore, $$\sum_{i = 1}^{k} \log x_i = \log \left( \prod_{i = 1}^{k} x_i \right) \leq \log \left( \prod_{i = 1}^{k} \frac{n}{k} \right) = k \log (n/k) \leq n = O(n)$$

Thanks to @JohnL. for pointing out that $k\log_{e}(n/k) \leq n$.

  • $\begingroup$ Yes, since $k\log(n/k)\le \frac ne$, for $n\ge e$. $\endgroup$
    – John L.
    Nov 25 at 18:41
  • $\begingroup$ @JohnL. Thanks! Can we also say that $k \log (n/k) \leq n$ for any value of $n$? I think so. $\endgroup$ Nov 25 at 18:51
  • 1
    $\begingroup$ Of course, since $\log(n/k)\lt0$ if $n\lt e$. (The base for $\log$ here and above is $e$). $\endgroup$
    – John L.
    Nov 25 at 18:55
  • $\begingroup$ @InuyashaYagami Thanks for the answer, how do you prove that the multiplication is maximum when the values are equal? $\endgroup$ Nov 25 at 19:10
  • 1
    $\begingroup$ @DaniMesejo Take a look at Jensen's inequality. If you want to prove it from scratch take two factors $a$ and $b$ such that $a<b$ and compare the product $a \cdot b$ with the product $(a+\varepsilon) \cdot (b-\varepsilon)$ for some sufficiently small $\varepsilon > 0$ (notice that the sum of the factors stays the same). $\endgroup$
    – Steven
    Nov 25 at 20:22

Your Answer

Dani Mesejo is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.