1
$\begingroup$

I've been trying to solve this recurrence relation in my advance algorithms paper. I've found that the Master method doesn't work.

I tried using an iterative method up to an extent, and then substituted $n = 2^{2^i}$ as below

http://postimage.org/image/624p28vn5/

Please can someone suggest a way to solve it. Any other method that works would also be appreciated!

2 Answers 2

2

Let $n=k2^i$ Therefore we get:$T(k2^i)=2T(k2^{i-1})+(k2^i)/\log(\log k+i\log(2))$

Now multiply both sides by $2^{-i}$ to get: $2^{-i}T(k2^i)=2^{-(i-1)}T(k2^{i-1})+k/\log(\log k+i\log(2))$ $2^{-i}T(k2^i)-2^{-(i-1)}T(k2^{i-1})=k/\log(\log k+i\log(2))$

Now sum both sides of the equation from i=1 to i=n and use the method of differences.

The solution:$T(k2^n)=2^{n}[T(k)+\sum\limits_{i=1}^{n}k/\log(\log k+i\log(2))]$

In case k=1, the solution becomes:$T(2^n)=2^{n}[T(1)+\sum\limits_{i=1}^{n}1/(\log(i)+\log(\log(2)))]$

  • 0
    I edited my answer to include a solution.2012-11-16
1

Actually the Master method does apply here and it predicts that $ T(n) \sim \frac{n}{\log\log n} \log_2 n \sim \frac{n}{\log\log n} \log n .$ We pick up the logarithmic factor because the number of subproblems ($2$) times the size of the subproblems is $n$.

It can also be done from first principles. First unwind the recursion to get $ T(n) \sim n \left( \frac{1}{\log(\log n - \log 2^0)} + \frac{1}{\log(\log n - \log 2^1)} + \frac{1}{\log(\log n - \log 2^2)} + \cdots \right)$ The inner term is the sum $ \sum_{k=0}^{\lfloor \log_2 n \rfloor - 1} \frac{1}{\log(\log n - k \log 2)}. $ Flip the index variable of the summation to obtain $ \sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{1}{\log(\log n - \lfloor \log_2 n \rfloor \log 2 + k \log 2)}. $ Now note that $ \left| \log n - \lfloor \log_2 n \rfloor \log 2\right| \le \log 2 $ so that this is asymptotic to $ \sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{1}{\log\log 2 + \log(1 + k)} \sim \sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{1}{\log(1 + k)}.$

We need the asymptotics of $\sum_{k=1}^m \frac{1}{\log(1 + k)}.$ We have a lower and an upper bound. $ \sum_{q=0}^{\lfloor \log_2 m \rfloor} \sum_{k=2^q}^{2^{q+1}-1} \frac{1}{\log(1 + k)} \le \sum_{k=1}^m \frac{1}{\log(1 + k)} \le \sum_{q=0}^{\lfloor \log_2 m \rfloor + 1} \sum_{k=2^q}^{2^{q+1}-1} \frac{1}{\log(1 + k)}. $ We simplify these to obtain $ \sum_{q=0}^{\lfloor \log_2 m \rfloor} \frac{2^q}{\log 2^{q+1}} < \sum_{k=1}^m \frac{1}{\log(1 + k)} < \sum_{q=0}^{\lfloor \log_2 m \rfloor + 1} \frac{2^q}{\log 2^q}. $ or $ \sum_{q=0}^{\lfloor \log_2 m \rfloor} \frac{2^q}{(q+1)\log 2} < \sum_{k=1}^m \frac{1}{\log(1 + k)} < \sum_{q=0}^{\lfloor \log_2 m \rfloor + 1} \frac{2^q}{q \log 2}. $ These two bounds show that $ \sum_{k=1}^m \frac{1}{\log(1 + k)} \sim \sum_{q=0}^{\lfloor \log_2 m \rfloor} \frac{2^q}{q}.$ To conclude note that $ \sum_{q=0}^{\lfloor \log_2 m \rfloor + 1} \frac{2^q}{q} \sim \frac{2^{\lfloor \log_2 m \rfloor}}{\lfloor \log_2 m \rfloor} \sim \frac{m}{\log_2 m}.$ This is because a sum of exponentials is its own asymptotic expansion, since with $S = \sum_{q=1}^p \frac{z^q}{q}$ we have $ \lim_{z\to\infty} \frac{S - \sum_{q=q_0}^p \frac{z^q}{q}}{z^{q_0}/q_0} = \lim_{z\to\infty} \sum_{q=1}^{q_0-1} z^{q-q_0}{q} \frac{q_0}{q} = 0.$ Finally recall that in our case we have $m = \lfloor \log_2 n \rfloor$ to obtain $ T(n) \sim n \frac{\log_2 n}{\log_2 \log_2 n} = n \frac{\log n}{\log \log_2 n} = n \frac{\log n}{\log \log n - \log \log 2} \sim n \frac{\log n}{\log \log n}.$

  • 0
    thanks Marko.. this is more clearer2012-11-17