1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ Yes, since $k\log(n/k)\le \frac ne$, for $n\ge e$. $\endgroup$
    – John L.
    Nov 25, 2021 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, 2021 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, 2021 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, 2021 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, 2021 at 20:22

Your Answer

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.