1
$\begingroup$

Prove that $T(n) = 2T(\frac{n}{2}) + \frac{n}{\log_2n}$ is $O(n\log_2\log_2n)$, where $T(1) = Θ(1)$.

I tried to form the Induction Hypothesis but didn't succeed in choosing the right one.

Try 1:

If we assume $0 ≤ ck\log_2\log_2k,\forall k < n$, must show $T(n) ≤ cn\log_2\log_2n$.

$$ T(\frac{n}{2}) ≤ c(\frac{n}{2})\log_2(\log_2n - 1),\because \frac{n}{2} = k < n$$ \begin{align} & T(n) ≤ cn\log_2(\log_2n - 1) + \frac{n}{\log_2n}\\ & ≤ cn\log_2\log_2n + \frac{n}{\log_2n}\\ \end{align} but this expression is never less than $cn\log_2\log_2n$, due to the positive $\frac{n}{\log_2n}$ term.

Try 2:

Assume $0 ≤ ck\log_2\log_2k - \frac{bk}{\log_2k}, \forall k < n$, must show $T(n) ≤ cn\log_2\log_2n - \frac{bn}{\log_2n}$.

$$T(\frac{n}{2}) ≤ c(\frac{n}{2})\log_2(\log_2n - 1) - \frac{bn}{2(\log_2n - 1)}, \because \frac{n}{2} = k < n$$ \begin{align} & T(n) ≤ cn\log_2(\log_2n - 1) - \frac{bn}{(\log_2n - 1)} + \frac{n}{\log_2n}\\ & ≤ cn\log_2\log_2n - \frac{bn}{\log_2n} + \frac{n}{\log_2n}\\ \end{align} If we factor the $\frac{-n}{\log_2n}$ out, we get $cn\log_2\log_2n - \frac{n}{\log_2n}(b - 1)$. Once again, it's never less than $cn\log_2\log_2n - \frac{bn}{\log_2n}$ because its $\frac{n}{\log_2n}$ negative factor is bigger.

I tried reforming the inductive hypothesis to be $ck\log_2\log_2k - \frac{2bk}{\log_2k}$, $ck\log_2\log_2k - \frac{bk}{2\log_2k}$, $ck\log_2\log_2k + \frac{bk}{\log_2k}$, but I can never get my expression bounded.

Any suggestions?

$\endgroup$
0

1 Answer 1

0
$\begingroup$

Let $S(n) = T(n)/n$, so that $$ S(n) = \frac{T(n)}{n} = \frac{2T(n/2)}{n} + \frac{1}{\log_2 n} = S(n/2) + \frac{1}{\log_2 n}. $$ Suppose now that $n = 2^k$, and suppose $S(1) = T(1) = C$. Then $$ S(2^k) = S(2^{k-1}) + \frac{1}{k}, $$ and so unrolling, we get $$ S(2^k) = \frac{1}{k} + \cdots + \frac{1}{\ell} + S(2^{\ell-1}). $$ In particular, taking $\ell = 1$, this gives $$ S(2^k) = \frac{1}{k} + \cdots + \frac{1}{1} + S(1) = H_k + C, $$ where $H_k$ is the harmonic number, well-known to satisfy $H_k = \ln k + O(1)$. Therefore if $n = 2^k$ then $$ T(n) = nS(n) = n\ln\log_2 n + O(n). $$ Using more accurate asymptotics of the harmonic number, we can find an even better approximation to $T(n)$, for example $$ T(n) = n\ln\log_2 n + (\gamma+C) n + \frac{1}{2} + O\left(\frac{1}{n}\right). $$

$\endgroup$
3
  • $\begingroup$ sorry for not being able to handle this given your hint. as I understood if I prove that $S(n)$ is $O(\log_2\log_2n)$, then $T(n)$ is $O(n\log_2\log_2n)$. but while trying to prove $S(n)$, I face the same problem of not being able to get rid of the fraction positive term. So far I've only seen the non-recurrent part as some standard functions, I searched the internet and never found one with a fraction instead. Also, if only $T(n/2)$'s factor was bigger than 2, I could've worked more with terms. Can you maybe give me links to similar problems or give another tiny hint? $\endgroup$
    – Mampac
    Feb 16, 2022 at 13:06
  • $\begingroup$ I’m sorry, but you’ll have to take it from here. Don’t try to plug anything into formulas. Take the recurrence as your starting point, and try to evaluate it exactly. $\endgroup$ Feb 16, 2022 at 13:22
  • 1
    $\begingroup$ assuming $S(n) ≤ c\log_2\log_2k$, $S(n) = c\log_2(\log_2n - 1) + \frac{1}{\log_2n} = c\log_2(\log_2n(1 - \frac{1}{\log_2n})) + \frac{1}{\log_2n} = c\log_2\log_2n + c\log_2(1 - \frac{1}{\log_2n})+ \frac{1}{\log_2n} ≤ c\log_2\log_2n + \frac{1}{\log_2n} - \frac{c}{\log_2n} ≤ c\log_2\log_2n$, as long as $c > 0$. Take $c = 1$, then $S(n) = O(\log_2\log_2n)$ $\endgroup$
    – Mampac
    Feb 17, 2022 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.