Prooving that T(n)=2∗T(⌊n/2⌋+17)+n is O(nlg(n))

Question

I want to solve this exercice : (lg(n) is the logarithm in base 2 in all the text) "Show that the solution of $T(n) = 2*T(⌊n/2⌋+17)+n$ is $O(nlg(n))$"

I tried everything I know but nothing worked. Here is what I did. First of all, I tried the substitution classical method. So I wrote $T(n) <= 2*c*(⌊n/2⌋+17)*lg(⌊n/2⌋+17)+n$ then I wanted to show that we had $T(n) <= c*n*lg(n)$. I wrote $T(n) <= (cn+34c)*lg(⌊n/2⌋+17)+n$ and then I am completely lost, it seems so difficult to show that this is <= to cnlg(n) I absolutely have no idea of what to do. I tried all kind of algrebic manipulation but absolutely nothing worked so I thought that maybe the method was not good and I had to switch to the others method I knew.

The second method I know is to try to add constants to your function, so I tried this $c*n*lg(n)-d$, the result was even worse, I got this : $T(n) <= 2*(c*(⌊n/2⌋+17)*lg(⌊n/2⌋+17)-d)+n <= (c*n+34c)*lg(⌊n/2⌋+17)-2d+n$ and I am supposed to show that this is $<= c*n*lg(n)-d$ ??? It is equivalent to $(c∗n∗lg(n)−d-((c∗n+34c)∗lg(⌊n/2⌋+17)−2d+n) >= 0)$ Honestly it is so complicated, I am just desperated, I clearly see that it is completely dumb and impossible to do it like that but I'm 100% stuck everytime and can't do a single exercise...

After this disappointment I decided to tried the third technique I knew, change of variables. So I proposed the change m = ⌊n/2⌋+17 so maybe we get rid of the ⌊n/2⌋ (honestly I just have no idea, I just try everything I know and every idea that I have, I am just completely unable to figure out what method I should use and to find a path to the solution )

I wrote $T(2*(m-17)) = 2*T(m)+(m-17)$. Let's write $S(m) = T(2*(m-17))$, we have $S(m) = 2*T(m)+(m-17)$ and then I recognized that we could maybe use the adding a constant ( second method ) technique to get rid of the 17 to the end ? So I wrote : $S(m) <= 2*(c*m*lg(m)-d)+(m-17) <= 2*c*m*lg(m)-2d+m-17$ As we want to prove that $S(m) <= c*m*lg(m)$ I want to try to prove : $2*c*m*lg(m)-2d+m-17 <= c*m*lg(m) ≡ c*m*lg(m)-(2*c*m*lg(m)-2d+m-17) >= 0 ≡ c*m*lg(m)-2c*m*lg(m)+2d-m+17 >= 0 ≡ c*m*lg(m)[1-2c]+2d+m-17 >= 0 $ And then I am completely blocked, it start to become so much complicated, so long and I know I am totally in the wrong direction Can someone help me please ? I don't understand what I need to do, which method I need to choose and why all my results are always so much complicated and so clearly wrong and stupids. Please help me. Thank you by advance. Thank you a lot.

Edit : After reading again the third technique application I did, I remark a problem in my variable change, I did m = ⌊n/2⌋+17 and concluded that we had n = (m-17)*2 but this is not true if n is odd... So I think my "proof start" try was even more wrong than I thought...

Answer 1

Concerning the recurrence

$$ T(n) = 2T(⌊n/2⌋+17)+n $$

making $n = 2^m$ and assuming $m >> 1$ we have

$$ T(2^m) = 2T(2^{m-1}+17)+2^m\approx 2T(2^{m-1})+2^m $$

now solving the recurrence

$$ R(m) = 2R(m-1)+2^m $$

we get

$$ R(m) = 2^m(m + c_0) $$

Taking $c_0 = 0$ and going backwards

$$ T(n) \approx n\log_2 n\ \ \ \text{asymptotically} $$

NOTE

Attached a MATHEMATICA script showing $(n, T(n))$ in red and the approximation $T(n)\approx n \log_2 n$ in blue

Clear[Rec, f]
f[n_] := n Log[2, n]
nmax = 2000;
nmin = 34;
Rec[n_] := Module[{}, If[n < nmin, Return[0]];
  If[n == nmin, Return[-34]];
  Return[2 Rec[Floor[n/2] + 17] + n]
  ]
tab = Table[{n, Rec[n]}, {n, nmin, nmax}];
gr1 = ListPlot[tab, PlotRange -> All, Filling -> Axis, PlotStyle -> {Thick, Red}];
gr2 = Plot[f[x], {x, nmin, nmax}, PlotStyle -> {Blue, Thick}];
Show[gr1, gr2, PlotRange -> All]

Answer 2

You have T(34) = 2T(34) + 34, therefore T(34) = -34. You can directly calculate T(k) for k = 33, 32, 31, … 3, 2, 1, 0 in that order.

Let S(n) = T(n+34), then S(n) = T (n + 34) = 2 T(n/2 + 34/2 + 17) + n + 34 = 2T(n div 2 + 34) + n+34 = 2 S(n div 2) + n + 34, and S(0) = -34. So you have

S(n) = 2 S(n div 2) + n + 34, S(0) = -34.

Calculate a few values of S(n) to see it becomes positive, then you can find and prove an upper bound for S(n), and that will give you an upper bound for T(n) for large n. Small n don’t matter since you are looking for big-O.