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?

Re: I need help solving a recurrence

Quote:

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$

Re: I need help solving a recurrence

Quote:

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?

Re: I need help solving a recurrence

Quote:

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{...}$

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.