Question

Solve this recurrence relation: T(n) = T(n-1) + T(n/2) + 1

Answer 1

 induction steps,

T(n)=T(n-1) + T(n/2) + 1

     =T(n-2) + 2T(n/2) + 2   ...

     =T(1) + (n-1) T(n/2) + n-1

using iteration tree method or master theorem,

 T(n)=theta(n^log2(n-1))

Comments

Does master theorem really apply to this one?

Is the second step really correct?

Answer 2

T(n)=T(n-1)+T(n/2)+1;

T(n)-T(n-1)=T(n/2)+1;

T(n-1)-T(n-2)=T(n-1/2)+1;

T(n-2)-T(n-3)=T(n-2/2)+1;

T(2)-T(1)=T(1)+1;

Add all the function together

T(n)-T(1)=(n-1)+T(1)-+[T(n/2)+ T(n-1/2)…T(1)],so T(n)=n+ [T(n/2)+ T(n-1/2)…T(2/2)];

Let we calculate the last parts

T(n/2)= T((n/2)-1)+T(n/4)+1= T(n-2/2)+T(n/4)+1

T(n/2)-T(n-2/2)= T(n/4)+1;

T(n-1/2)-T(n-3/2)= T(n-1/4)+1;

T(n-2/2)-T(n-4/2)= T(n-2/4)+1;

T(3/2)-T(1/2)=T(3/4)+1=T(1)+1

T(2/2) =T(1) 

So, the T(n/2)+ T(n-1/2)…T(1)=[ T(n/4)+ T(n-1/4)+…T(3/4)]+n;

T(n/4)+ T(n-1/4)+…T(3/4)= T(n/8)+T(n-1/8)+... T(5/8)

Finally, we can get T(n)=theta((n)^log₂n)

Comments

Looks pretty close, but not sure it establishes theta relationship.  Can substitution (guess and prove method) provide a clue?

---

I suppose is not theta relationship, but big O((n)^log2n).
so T(n)<=k*(n)^log2n
Verify T(n-1)+T(n/2)=k(n-1)^log2_n-1+k(n/2)^log2_n/2+1<=k*(n)^log2n
k(n-1)^log2_n-1+k(n/2)^log2_n/2+1<kn^((log2_n)-1)+(k/n*2^log2_n-1)*n*log2_n
=(k/n+k/n*2^log2_n)*(n)^log2n<=k*(n)^log2n
when (2^log2_n-1+1)<n*2^log2_n-1,this function is achieved
obvious when n is positive infinite,this function always be successful
so we can get T(n)=O((n)^log2n)

Answer 3

The problem is at least O(n^2). So I suppose that the T(n/2) contributes log(n).

 if T(n)∈O(n^log(n)). T(n)≤Mn^log(n)

As we Known:T(n)=T(n−1)+T(n/2)+1 <T(n)=T(n−1)+T(n/2)+n

substitute known recursion into T(n)≤Mn^log(n) :

T(n−1)+T(n/2)+n≤Mn^log(n)

T(n−1)+T(n/2)≤Mn^log(n)−n

hypothesis again:

T(n−1)≤M(n−1)^log(n−1)
T(n/2)≤M(n/2)^log(n/2)

M(n−1)^log(n−1)+M(n/2)^log(n/2)≤Mn^log(n)−n

M((n−1)^log(n−1)+(n/2)^log(n/2)−n^log(n))≤−n
M(n^log(n)−(n−1)^log(n−1)−(n/2)^log(n/2))≥n

At this point, it's pretty obvious that we've found a solution. Let M=1.
(n^log(n)−(n−1)^log(n−1)−(n/2)^log(n/2)≥n

Therefore we can conclude that T(n)∈O(n^log(n)).

Answer 4

We can divide it into 

G(n) = G(n-1) + O(1)

H(n) = H(n/2) + O(1)

 

For G(n) = G (n-1) + O(1)

        =G(n-1) + O(1) + O(1)

     …

     So G(n) = G(0) + O(n) 

    So G(n) = O (n).

 

For H(n) = H(n/2) + O(1)

    Using Master Theorem, c = 0 = log_b a  

    So H(n) = theta(logn)

 

For T(n) = G(n) + H (n), we take the large one, 

T(n) = O(n)

Comments

Does this match empirical results?

Answer 5

T(n) = T(n-1) + T(n/2) + 1

Claim

T(N) ≤ C for N ≤ n

Proof

T(N) ≤ T(N-1) + T(N/2) + 1

T(N) ≤ C - 1 + C/2 + 1         // This whole term is still a constant

T(N) ≤ C

Therefore, T(n) = C = O(1)

Comments

But the empirical results don't quite match this, right?  So, this analysis must be wrong somewhere!

Answer 6

I am using estimation method, let our time complexity be x,

T(n) = 2T (n - 1) + 1 > x > T(n) = 2T(n/2) + 1

For T(n) = 2T(n/2) +1

using Master Theorem, we get O(n).

For T(n) = 2T (n - 1) + 1

We use Tree unfolding Method, we notice a pattern of 

1 + 2+ 2² + 2³ +.......+ 2ⁿ⁺¹

Now that's in the form of Geometric Progression, 

So, 1(2ⁿ⁺¹ - 1) / 2 - 1 = 2ⁿ⁺¹ - 1

So, this is O(2ⁿ)

Our Time complexity lies between 2ⁿ > x > n

Answer 7

T(n) = T(n-1) + T(n/2) + 1

Using estimation method, we get

R(n) = 2R(n-1) + 1 & S(n) = 2S(n/2) + 1

Solving using the Master's Theorem we get, 

R(n) = O(n*2ⁿ)  & S(n) = n

Therefore, the time complexity is (n*2ⁿ) in the worst case.