a better guess on upper bound

Question

It's a question from 《introduction to algorithms》whose number is 4.4-5 and is described like this:

Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = T(n-1) + T(n/2) + n.Use the substitution method to verify your answer.

I found it is difficult to me to calculate the recursion tree's recurrence. The answer I gave

Math.pow(2,n)

seems too loose.Maybe there is some better guess existed.Thanks for any help.

Accept some answers to some of the questions you asked. People are less inclined to help people who don't give credit where credit is due. — Bernhard Barker, Jan 07 '13 at 22:38
@Dukeling:Thank you.I haven't noticed this actually.I will keep this in mind.Really appreciate your advice. — tuan long, Jan 08 '13 at 02:07
@tuanlong: Up instead of down? Ok :/ Then `T(1) = T(0) + T(1/2) + 1 = T(0) + T(1) + 1`, so `T(0) = -1`. But what is `T(1)` then? — , Jan 08 '13 at 02:35
@Tinctorius:T(0) not existed.T(1) is a constant.You'd better review chapter 4 of 《introduction to algorithms》, then you will know what I mean better.Thanks for your help. — tuan long, Jan 08 '13 at 03:44
@tuanlong: And what about the many people who do not own a copy of that book? Are they just supposed to guess the information missing from your question? — , Jan 08 '13 at 12:42
@Tinctorius:I'm sorry to make you unhappy and I really apprecited your help since I have got a lot of help here.I also wish I can use what I have learned here to help anyone someday.I just mean to say that if you have read that chapter you will understand this question more deeply. — tuan long, Jan 09 '13 at 12:04

maxim1000 · Accepted Answer · 2013-01-10T15:19:36.010

12

Hope I did no mistakes :)

let's A(n)=T(n/2)+n

0. T(n)=T(n-1)+A(n)=T(n-2)+A(n-1)+A(n)=...=A(1)+A(2)+...+A(n)
   T(n)=sum[1..n]A(n)
   T(n)=sum[i=1..n]T(i/2)+sum[i=1..n]i

assuming n/2 is integer division, T(n/2)=T((n+1)/2) for even n, so the first sum consists of two equal halves: T(1)+T(1)+T(2)+T(2)+...

1. T(n)=2*sum[1..n/2]T(i)+n*(n-1)/2

since T(n)<=T(m) for every n<=m

2. T(n)<=n*T(n/2)+n*(n-1)/2

since T(n/2)>=n/2>=(n-1)/2

3. T(n)<=n*T(n/2)+n*T(n/2)=2*n*T(n/2)

let's consider this for only n=2^k, since T is monotonous: n=2^k and U(k)=T(2^k)

4. U(k)<=2*(2^k)*U(k-1)=2^(k+1)*U(k-1)

let L(k)=log2 U(k)

5. L(k)<=k+1+L(k-1)

just like we did between step0 and step1

6. L(k)<=k*(k-1)/2+k=k*k/2-k/2+k<=k*k

7. U(k)=2^L(k)<=2^squared(k)

8. T(n)=U(log2 n)<=2^squared(log2 n)

edited Jan 10 '13 at 15:19

answered Jan 10 '13 at 14:09

maxim1000

6,297
1
23
19

+1 Clever! I couldn't find a solution but it seems like you did! I am still a bit lost though, could you please explain your first step. :) – user1884905 Jan 10 '13 at 14:42
2

I've added some details for the first step – maxim1000 Jan 10 '13 at 14:51
1

it seems the upper bound can be improved even more - I've updated items after #3. – maxim1000 Jan 10 '13 at 15:20
Thank you very much, really surprised to see your answer since I haven't come here for several days.I had been thinking no one would help me to resolve this question.It's really a grate place here. – tuan long Jan 15 '13 at 09:40
After step 2 , why you took n*T(n/2) instead of n/2*T(n/2)? Also after step 3 only can not we can try to solve the recurrence? Which will.come out to be n^logn/(2^((lgn*(1+lgn)/2))). – V K May 04 '20 at 04:55

score 1 · Answer 2 · edited May 23 '17 at 11:45

The recursion relation seems to give rise to a sub-exponential and super-linear computation-time, which means that any chosen base would work as an upper bound given a large enough n.

Your choice of 2^n is a good answer and possibly the one they were looking for in the book. It is a simple solution that is valid even for quite small values of n. (Still, I understand why you are asking the question because it does grow much faster than T(n) even for moderately large n.)

Given T(1) = 1 (or some other constant) the recursion equation gives us the running time as follows for the first few values of n.

T(1) = 1          n^1 = 2
T(2) = 4          n^2 = 4
T(3) = 11         n^3 = 8
T(4) = 19         n^4 = 16
T(5) = 35         n^5 = 32
T(6) = 52         n^6 = 64
T(7) = 78         n^7 = 128
T(8) = 105        n^8 = 256
T(9) = 149        n^9 = 512

We can see that the choice of 2^n as an upper limit is valid for all values T(6) and above.

If you want a lower bound than 2^n you could choose a lower base (with the trade-off that it will only be valid for higher numbers of n). But I must add that it will still be basically the same solution as the one you already have.

Any base larger than one would do but to be a bit more specific we could for example see that the recursion equation T(n) = T(n-1) + T(n/2) + n is bounded by the equation T(n) = T(n-1) + T(n-2) for n>5.

This is the same recursion relation as for the Fibonacci sequence and following the steps in the answers to this question it has a computational complexity matching the golden ratio (1+sqrt(5))/2 = 1,618 to the power of n.

Plotting the actual values we can see for which n the value of T(n) is bounded by ((1+sqrt(5))/2)^n. From the figure it seems to be values n=13 and above.

Computational complexity of algorithm.

All this said, I have thought a bit about approximating the running time with some sub-exponential function. It doesn't seem like it can be easily done and as I said I believe you have found the expected answer.

Thanks for your analisis.I have contributed here less while having got a lot of kindness here.I need to grow more fast and be able to help anyone needs help as soon as possible. — tuan long, Jan 15 '13 at 09:44
@tuanlong You are welcome! (Even if my answer was not totally correct.) :) I can see that you have not cast any votes. I would recommend that you go through your questions and up-vote answers that have helped you. Up-voting and accepting answers is a good way to show your appreciation here on stackoverflow. — user1884905, Jan 15 '13 at 10:05
I have been here not for a long time and noticed functions of "accept" and "vote" recently.I will try them, thank you. — tuan long, Jan 15 '13 at 10:53

a better guess on upper bound

2 Answers2