# I need help solving a recurrence

• Sep 23rd 2012, 01:39 PM
restin84
I need help solving a recurrence
assuming that n is a power of 2 $T(n) = (2 + \frac{1}{\log{n}})T(n/2)$ for $n >= 2$ with $T(1)= 1$

Its for an algorithms course and the answer needs to be in asymptotic notation.

I tried repeated substitution but things are getting complicated pretty fast. It does produce some pattern but it is not jumping out at me. Does anyone have some advice on an alternative?
• Sep 23rd 2012, 04:22 PM
MaxJasper
Re: I need help solving a recurrence
Quote:

Originally Posted by restin84
assuming that n is a power of 2 $T(n) = (2 + \frac{1}{\log{n}})T(n/2)$ for $n >= 2$ with $T(1)= 1$Its for an algorithms course and the answer needs to be in asymptotic notation. I tried repeated substitution but things are getting complicated pretty fast. It does produce some pattern but it is not jumping out at me. Does anyone have some advice on an alternative?

Check this out:

$T\left[2^k\right]=\prod _{i=1}^k \left(2+\frac{1}{\text{Ln}\left[2^i\right]}\right)$ :::: $T[1] = 1$,.... $k\geq 1$
• Sep 23rd 2012, 06:18 PM
restin84
Re: I need help solving a recurrence
Quote:

Originally Posted by MaxJasper
Check this out:

$T\left[2^n\right]=\prod _{i=1}^n \left(2+\frac{1}{\text{Ln}\left[2^i\right]}\right)$ :::: $T[1] = 1$,.... $n\geq 2$

So I guess that since I'm seeing $T[n^2]$ I should be using a change of variable?
• Sep 23rd 2012, 06:30 PM
MaxJasper
Re: I need help solving a recurrence
Quote:

Originally Posted by restin84
So I guess that since I'm seeing $T[n^2]$ I should be using a change of variable?

You said n is a power of 2 : n=2,4,8,... $\to 2^k,k=1,2,3,\text{...}$
• Sep 25th 2012, 07:09 AM
emakarov
Re: I need help solving a recurrence
Let P(k) = (2 + 1/1)(2 + 1/2) ... (2 + 1/k) and P(0) = 1. Then $T(2^k) = P(k)$. It is clear that $P(k)\le 3^k=(2^k)^{\log3}$, so $T(n)\le n^{\log3}\le n^{1.6}$. It is possible to show by induction that $P(k)\le2^k\cdot k$, so $T(n)\le n\log n$, which is a much better upper bound.