1
$\begingroup$

Let $$X(n) = \displaystyle\sum_{k=1}^{n}\dfrac{1}{k}.$$ $$Y(n) = \displaystyle\sum_{k=1}^{n}k^{1/k}.$$ $$Z(n) = \displaystyle\sum_{k=1}^{n}k^{k}.$$


For the first, I don't have a formal proof but I know that $X(n)\in \cal{O}(\log n)$. For the rest, I think $Y(n)\in \cal{O}(n)$ and $Z(n)\in \cal{O}(n)$.


How to determine the asymptotic behavior of theses summations?

How to calculate the complexities with a formal proof?

$\endgroup$
  • $\begingroup$ Note that $Z(n)\ge n^n.$ $\endgroup$ – mfl Jul 10 '14 at 14:58
  • $\begingroup$ The integral test should give you upper and lower bounds on $X(n)$. You should be able to upper and lower bound (with constants) the terms in $Y(n)$. As mfl has observed, the last term in $Z(n)$ dominates -- all you have to do is show this. $\endgroup$ – Eric Towers Jul 10 '14 at 15:02
  • $\begingroup$ The first is easy to compare with $\int_{1}^n \frac{dx}{x} = \log n$. It's basically a Reimann sum of this integral. $\endgroup$ – Thomas Andrews Jul 10 '14 at 15:11
  • $\begingroup$ I suspect it is not hard to show that $Z(n)=O(n^n)$. $\endgroup$ – Thomas Andrews Jul 10 '14 at 15:13
2
$\begingroup$

Assuming $k,n \in \mathbb{Z}_{>0}$ throughout.

X(n)

$$\ln n = \int_{1}^n \frac{\mathrm{d}x}{x} \leq \sum_{k=1}^n \frac{1}{k} \leq 1+\int_{1}^{n-1}\frac{\mathrm{d}x}{x} = 1+ \ln (n-1) < 1+\ln(n)$$

Therefore $X(n) \in O(\log n)$.

Y(n)

We find the largest possible value of the summand by finding the largest possible value of the expression as if the variable were a real number. $D_x(x^{1/x}) = 0 \implies x = \mathrm{e}^{1/\mathrm{e}} < 3/2$ and since the second derivative is negative here, this is a maximum. There is also no challenge in using the binomial theorem to show that the summands approach 1 from above as $k$ increases. We have $1 \leq k^{1/k} \leq 3/2$.

$$ (1)n \leq \sum_{k=1}^n k^{1/k} \leq (3/2) n $$

Therefore $Y(n) \in O(n)$.

Z(n)

$$n^n \leq \sum_{k=1}^n k^k \leq n^n + (n-1)(n-1)^{n-1} = n^n + (n-1)^n < 2 n^n $$

Therefore $Z(n) \in O(n^n)$.

$\endgroup$
  • $\begingroup$ +1, nice. @x.y.z..., note that these arguments additionally show that $X(n) \in \Theta(\log n)$, $Y(n) \in \Theta(n)$, and $Z(n) \in \Theta(n^n)$. $\endgroup$ – Antonio Vargas Jul 10 '14 at 16:49
0
$\begingroup$

I don't know how to use the integral test. As suggested by @Eric and others, I am trying to answer my question.

$$\begin{equation}\begin{split}1\leqslant k\leqslant n&\Leftrightarrow\dfrac{1}{n}\leqslant \dfrac{1}{k}\leqslant 1\\&\Leftrightarrow1\leqslant X(n)\leqslant n\\&\Rightarrow X(n)\in\cal{O}(n).\end{split}\end{equation}$$ which is not a tight approximation.


$$\begin{equation}\begin{split}1\leqslant k\leqslant n&\Leftrightarrow1\leqslant k^{1/k}\leqslant n^{1/k}\\&\Leftrightarrow n\leqslant Y(n)\leqslant \sum_{k=1}^{n}n^{1/k}=n+o(n)\\&\Rightarrow X(n)\in\Theta(n).\end{split}\end{equation}$$


I don't know what to do with $Z(n)$ because I will get $\displaystyle\sum_{k=1}^{n}n^k$.

$\endgroup$

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.