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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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$.
answered Nov 25, 2021 at 18:19
-
$\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$– StevenNov 25, 2021 at 20:22