Help Solve Tricky Recurrence Relation

Question

I have the following, and need to write it in terms of x, and n or provide a bound on its complexity (Big O), any ideas? (n is a constant, $1≤x<n$)

$ E(x)=1+E(x-1+\frac{x}{n}-\frac{x^2}{2n})\\ E(x\leq2)=1 $

Answer 1

This is not strictly speaking an answer to your question but a step forward in the understanding of the goal.

I have programmed the recursive functional relationship : the recursive calls all end up in a finite number of steps (a major step that you will have to establish, common to all recursive definitions) and one obtains the following figure :

which looks to be very close to a function with equation :

$$y=\lceil a(1-e^{-bx}) \rceil$$

for some constants $a$ and $b$ where $\lceil A \rceil$ is the smallest integer at least equal to $A$.

Here is the Matlab program that has generated this figure :

   function Erecur;
   n=400;S=[];
   for x=1:0.01:n;
      S=[S,E(x)];
   end;
   plot(1:0.01:m,S,'r');
   %%%
   function y=E(x)
   n=400;
   if x<2
      y=2;
   else
      y=1+E(x-1+x/n-(x.^2)/n);
   end;