dionysus Posted December 2, 2003 Share Posted December 2, 2003 Find the asymptotic bound to the following function: T(n) = T(n/2) + T(n/4) + 1. I'll give in my solution once I start receiving answers. Quote Link to comment Share on other sites More sharing options...
Nkruti Posted December 2, 2003 Share Posted December 2, 2003 Would the answer be O(n)? Quote Link to comment Share on other sites More sharing options...
dionysus Posted December 3, 2003 Author Share Posted December 3, 2003 Yes O(n) is the right answer. I worked it out using recursion trees. T(n) -----> T(n/2) ----> T(n/4) | | | --------> T(n/8) | -----> T(n/4) -----> T(n/8) | --------> T(n/16). and so on. With some handwaving, one can assert the following, the number of nodes at depth I is less than or equal to 2^i. And the cost of level I is 1 per node on that level. So the total cost = Sum_{i=0}^{depth} 2^i = 2^{depth + 1} - 1. Now depth = log_2 n, so that total cost = 2n - 1 = O(n). Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.