I'm trying to figure out what's the asymptotic complexity for the following sums:
$$\sum_{k=1}^n lg^s k$$
$$\sum_{k=1}^n k^rlg^s k$$
s and r are positive constants.
I think i should be using integrals for these, but given this: https://en.wikipedia.org/wiki/List_of_integrals_of_logarithmic_functions, I just can't find a way to solve these.
Any help will be appreciated,
On
Hint. You may compare your sums with related integrals. $$ \int_1^n (\ln x)^sdx-(\ln (n+1))^s\leq\sum_{k=1}^n (\ln k)^s \leq\int_1^n (\ln x)^sdx,\quad n\geq1. $$ Then observe that, as $n \to \infty$,
$$ \begin{align} \int_1^n (\ln x)^s\:dx&=n\:(\ln n)^s-s\int_1^n (\ln x)^{s-1}\:dx\sim n\:(\ln n)^s. \end{align} $$
Similarly, as $n \to \infty$,
$$ \begin{align} \int_1^n x^r(\ln x)^s\:dx&=n^r\:(\ln n)^s-s\int_1^n x^{r-1}(\ln x)^{s-1}\:dx \sim n^r\:(\ln n)^s. \end{align} $$
Using integrals which needed to be guessed looked overly complicated for this problem, i asked a friend at work and we believe that we came up with an answer that does not involve integrals:
$\sum_{k=1}^nlg^sk = \sum_{k=1}^{\lfloor n/2\rfloor}lg^sk+\sum_{k=\lfloor n/2\rfloor}^nlg^sk\ge$
$\sum_{k=1}^{\lfloor n/2\rfloor}0+\sum_{k=\lfloor n/2\rfloor}^nlg^s(n/2)=$
$0+n*lg^s(n/2)=\Omega(n*lg^s(n))$
I know the last part is true, but i don't really know how to prove it...
A similar trick can be applied for the upper bound.