# Thread: I need help solving a recurrence

1. ## I need help solving a recurrence

assuming that n is a power of 2 $\displaystyle T(n) = (2 + \frac{1}{\log{n}})T(n/2)$ for $\displaystyle n >= 2$ with $\displaystyle 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?

2. ## Re: I need help solving a recurrence

Originally Posted by restin84
assuming that n is a power of 2 $\displaystyle T(n) = (2 + \frac{1}{\log{n}})T(n/2)$ for $\displaystyle n >= 2$ with $\displaystyle 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:

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

3. ## Re: I need help solving a recurrence

Originally Posted by MaxJasper
Check this out:

$\displaystyle T\left[2^n\right]=\prod _{i=1}^n \left(2+\frac{1}{\text{Ln}\left[2^i\right]}\right)$ ::::$\displaystyle T[1] = 1$,....$\displaystyle n\geq 2$
So I guess that since I'm seeing $\displaystyle T[n^2]$ I should be using a change of variable?

4. ## Re: I need help solving a recurrence

Originally Posted by restin84
So I guess that since I'm seeing $\displaystyle T[n^2]$ I should be using a change of variable?
You said n is a power of 2 : n=2,4,8,...$\displaystyle \to 2^k,k=1,2,3,\text{...}$

5. ## Re: I need help solving a recurrence

Let P(k) = (2 + 1/1)(2 + 1/2) ... (2 + 1/k) and P(0) = 1. Then $\displaystyle T(2^k) = P(k)$. It is clear that $\displaystyle P(k)\le 3^k=(2^k)^{\log3}$, so $\displaystyle T(n)\le n^{\log3}\le n^{1.6}$. It is possible to show by induction that $\displaystyle P(k)\le2^k\cdot k$, so $\displaystyle T(n)\le n\log n$, which is a much better upper bound.