Bound -> polynomial ?

[wood]

If T(0) = T(1) = 1, each of the following recurrences for n >= 2 defines a function T on the nonnegative integers. Which of the following CANNOT be bounded by a polynomial function?

 

(A) T(n) = 3T(|_ n/2 _|) + n^2

 

(B) T(n) = 4T(|_ n/2 _|) + n

 

© T(n) = T(|_ 7n/8 _|) + 8n + 1

 

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

 

(E) T(n) = T(n - 1) + n^2

 

 

PS: |_ a _| denotes the floor function on a.

[rafi_dery]

(D) is exponential :

 T(n)=O(2^|_n/2_|) 

[wood]

Rafi, good job!

 

Can you please elaborate on that one?

 

Thanks,

Wood

[ushak]

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

 

lets say T(0) = T(1) = 1

then

T(2) = 2*1 + 1 = 3 = 2^(2) - 1

T(3) = 2*3 + 1 = 7 = 2^(3) - 1

T(4) = 2*7 + 1 = 15 = 2^(4) - 1

etc., etc..

 

for T(n) , the value = (2^n) - 1

 

Hence this T(n) is exponential..

Rafi - do you have a different explanation for this.. let us know if so.

 

Thanks,

Usha

 

 

 

[wood]

Usha,

 

I'm not getting your explanation. Ex:

 

T(3) = 2*T(3-2)+1 = 2*T(1)+1 = 2*1+1 = 3 (it is T(n-2) and not T(n-1)) !

 

Wood

[The_Wonderful_Vipul]

Hey,

 

i have another explanation.

 

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

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

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

and so on .... till T(n-2i) = T(0) i.e. I = n/2

 

Consider overhead at each level : it grows like 1, 2, 4, 8 .. i.e O(2^i)

 

Hence the growth = O(2^n/2)

 

did you get it,

Vipul.

 

 

[jaideep]

Hey wood,

 

As usual a nice one. Although everyone over here solved it but in case anybody wants a refresher course on Recurrences I would suggest to go through "Introduction to Algorithms" by Thomas Cormen, and Ronald Rivest Chp 4.

 

It has it all nicely specially the master theorem part which helps a lot in the elimination procedure.

 

Guys keep pouring in,

Jaideep

 

[wood]

Vipul: Thanks for the explanation...

 

Jaideep: thanks for the link. I have the book and I'll take a look at it when I get a chance.

 

Wood

[wood]

Jaideep,

 

With the master theorem, we are able to eliminate A, B, and C, right?

 

(A) n^log2 3 = n^1.585. Since f(n) = n^2 is greater than n^1585, then the upper bound is O(f(n)) = O(n^2)

 

(B) n^log2 4 = n^2. Since f(n) = n is smaller than n^2, then the upper bound is O(n^log2 4) = O(n^2)

 

© n^log8/7 1 = n^0 = 1. Since f(n) = 8n + 1 is greather than 1, then the upper bound is O(8n + 1) = O(n)

 

Which method did you use to eliminate (E) or to find out that (D) is the answer?

 

Rafi, we'd appreciate if you could share your reasoning on that one.

 

Thanks,

Wood

[jaideep]

Hey Wood,

 

Well I used Master Theorem to eliminate A and B

C I used iteration method to recursively substitute the T(n) values and finally you see a trend which gives ith term as (7^i/8^(i-1))*n + (i+1). Summation of which is a gemetric series.

 

E I again used substitution method getting a series of n^2 + (n-1)^2 ... giving O(n^3).

 

Finally for (e) solve it via substitution method which gives a geometric series with a ratio of 2. Something like 2^3 T(n-3.2)+2^2 + 2 + 1 .

This on Summation gives O(2^((n+1)/2)) which is again O(2^n/2) clearly exponential

 

cheers,

Jaideep

[wood]

Is (E) = O(n^3) ??

 

[rafi_dery]

wood: I'm not familiar with that master theorem you mentioned. can you cite it in here?

about (E) it is absolutely almost n^3, since T(0)=T(1)=1. it should be smthng like n^3 - n^2 + 2

 

The explanation for my answer is the same as Vipul's:

 

T(n) = 2T(n-2) + 1 = 2{ 2T(n-4) + 1} +1 = 2 { 2 { 2T(n-6) +1 } +1 } +1

 

say we get to T(0) or T(1) we have been through n/2 multiplications of 2, thus T(n) = o(2^ 0.5n)

 

[wood]

Thanks Rafi and Jaideep!!

 

Rafi: here's the theorem:

 

Given T(n) = aT(n/b) + f(n),

 

where we interpret n/b to mean either floor(n/b) or ceiling(n/b). Then T(n) can be bounded asymptotically as follows.

 

1. If f(n) = O(n^(log_b a-e)) for some constant e>0, then T(n) = Theta(n^(log_b a)).

 

2. If f(n) = Theta(n^(log_b a)), then T(n) = Theta(n^(log_b a) lg n).

 

3. If f(n) = Omega(n^(log_b a+e)) for some constant e>0, and if af(n/b)

 

Refer to Introduction to Algorithms (Cormen) or the following links:

 

http://cs.gmu.edu/~pwang/Fall03/cs583/RR.pdf

http://theory.lcs.mit.edu/~sweis/6.046/mastermethod.pdf

http://www.cs.huji.ac.il/~dast/slides/master.pdf

 

Wood

 

[napoleon]

Hi

Clearly the answer is D. You can solve D and E, by telescopic reduction. However I have found a little problem with B. The recurrence T(n) = 4T(|_ n/2 _|) + n seems to satisfy the third case from the Master theorem, but the condition

"af(n/b)

The interesting part is that I have solevd the recurrence using the tree method from Cormen and got an exponential answer T(n) = (4^(n+1) - 3n + 4)/9.

The method counts the number of nodes on each level of the complete tree formed by this recurrence. For this paricular problem, we have:

level 0: 1 node

level 1: 4n nodes

level 2: 16(n-1) nodes

-----------------------

level k: 4^k(n-k) nodes

 

We can calculate the sum and we obtain the exponetial execution time. Could anybody find the error in this recurrence logic?

Thank you

[Nkruti]

Hi Napoleon,

 

Firstly I think Question B satisfies condition 1 of the master theorem.

 

Coming to the solution using recursion trees.

My drawing skills are sloppy. So let me try and explain it this way.

The subproblem size at depth i is (2^i) n.

the subproblem size will hit n=1 at depth i=log_2 n i.e (log n with base 2)

Total cost at level i =(2^i) n

The last level at depth (log_2 n) has 4^(log_2 n) nodes i.e n^2 nodes each contributing cost T(1) , for a total cost of n^2 T(1) which is theta(n^2)

 

Now if we compute the total cost

T(n)= n+2n+4n + ........... +2^(log_2 n -1) n + theta(n^2)

 

 

This is what I think the summation should look like. Please correct me if I am wrong.

[napoleon]

Hi Nkruti

You are absolutely right in your answers. I have reviewed the recurrence tree method from Cormen and rethought my computation, we get a T(n) = theta(n2). Thank you very much for your prompt answer.