0
$\begingroup$

Find tight bounds to $T(n)=2T(\frac n 2) +\frac{n}{\log n}$

The upper bound: $\displaystyle 2T(\frac n 2) +\frac{n}{\log n} \le T(\frac n 2) +n = \sum_{i=0}^{\log n}\frac n {2^i} \le n\sum_{i=0}^{\log n}\frac 1 {i}=\Theta (n\log \log n)$.

But I can't figure out how to do the lower bound, I either get stuck like this:

$\displaystyle T(n)\ge T(\frac n 2)+\frac 1 {\log n} = \sum_{i=0}^{\log n} \frac 1 {\log n - i}$

Or get an expression too small.

Note, I don't want to solve it, just find tight bounds.

$\endgroup$
7
  • $\begingroup$ Note that $$2^{-k}T(2^k)=T(1)+\frac1{\ln2}\sum_{i=1}^k\frac1i\implies T(2^k)=2^k\log_2 k+O(2^k)$$ Although this is far from being mathematically guaranteed, you might be expected to deduce from this that, for some explicit $O(n)$ which can be quantified in terms of $T(1)$, $$T(n)=n\log_2\log_2n+O(n).$$ $\endgroup$ – Did Nov 16 '15 at 13:14
  • $\begingroup$ I don't see how this is equal to $n\log \log n$... Also how did the $2^k$ get to the $\log k$? @did $\endgroup$ – shinzou Nov 16 '15 at 13:19
  • $\begingroup$ $n=2^k\implies 2^k\log_2k=\ldots$ $\endgroup$ – Did Nov 16 '15 at 13:20
  • $\begingroup$ @did When asked to find bounds, shouldn't we bound it from above and below seperatly? $\endgroup$ – shinzou Nov 16 '15 at 13:30
  • $\begingroup$ And this is exactly what my comment shows how to find since there exists explicit bounds of the harmonic numbers in terms of logarithms, say $$\ln n<\ln(n+1)\leqslant\sum_{k=1}^n\frac1k\leqslant1+\ln n.$$ $\endgroup$ – Did Nov 16 '15 at 13:35
1
$\begingroup$

Set $n=2^k$ and $g(k) = T(n)$. We then have \begin{align} g(k) & = 2g(k-1) + \dfrac{2^k}k = 4g(k-2) + \dfrac{2^k}{k-1} + \dfrac{2^k}k = 2^k g(0) + \sum_{l=1}^k \dfrac{2^k}l = 2^kg(0) + 2^k H_k\\ & \sim ng(0) + n\log(k) + n\gamma = n(g(0)+\gamma) + n\log(\log(n)) \end{align}

$\endgroup$
1
  • $\begingroup$ Why is it $g(k-1)$ and not $g(2^{k-1})$? also what is $H_k$? $\endgroup$ – shinzou Nov 17 '15 at 19:53

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.