Register

If lower bound and upper bound of a recurrence relation are not asymptotically equal, then is it possible for it to have a theta notation?

• retagged by
452 views

1 Answer

4 votes
4 votes

No.

See this question from CLRS 3rd edition, page 53 (page 74 if including the cover, index and all)

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
2 answers
3
Shimpy Goyal asked Jun 27, 2015
1,186 views
what should b lower bound if not given i consider (0 ,0) but no option then how to procedd here?
Consider an array A[20, 10], assume 4 words per memory cell and the base address of array A is 100. What is the address of A[11, 5] ? Assume row major storage. (A) 560  (B) 565  (C) 570  (D) 575
Consider an array A[20, 10], assume 4 words per memory cell and the base address of array A is 100. What is the address of A[11, 5] ? Assume row major storage.(A) 560  (...
User Avatar
3 votes
3 votes
2 answers
4
SomnathKayal asked Apr 14, 2016
895 views
A better guess on upper bound
It's a question from Cormen book Exercise 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(\frac{n}{2})+n$
It's a question from Cormen book Exercise 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)+...
User Avatar
Link Copied!