nonevent99 Posted November 1, 2003 Share Posted November 1, 2003 function f(n) { if (n return f(n-1) + f(n-2); } What is the run-time R(n) as a function of f(n)? A) Theta(f) B) Theta(lg f base 2) C) Theta(log f base phi) D) Theta(f^p) for some integer p > 1 E) None of the above What is the run-time R(n) as a function of f(n) if O(1) memoization is added? Quote Link to comment Share on other sites More sharing options...
wood Posted November 2, 2003 Share Posted November 2, 2003 Is the answer (A) ? f(n) = f(n-1) + f(n-2) R(n) is the number of nodes in a binary tree with n-1 levels. Considering the first call and its subsequent calls 2^(n-1)-1, the R(n) is O(2^(n-1)). So, R(n) as a function of f(n) is Theta(f). If O(1) memoization, R(n) will be Theta(n) ? Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 2, 2003 Share Posted November 2, 2003 I think u're right wood, good job Quote Link to comment Share on other sites More sharing options...
Laks Posted November 2, 2003 Share Posted November 2, 2003 Hey Wood, Great job... I would just like to point out ont thibg here about fib numbers.... f(n) f(n) = O(2^n-1)...... nothing wrong with your funda... just like to add though... Cheers' Laks Quote Link to comment Share on other sites More sharing options...
wood Posted November 2, 2003 Share Posted November 2, 2003 You're right Laks... The fibonnacci series is O(phi^(n-1)), but we bound it to O(2^(n-1)) for simplicity! Thanks for pointing that out. Wood Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 2, 2003 Author Share Posted November 2, 2003 I think you guys have the right answer. Good job. The formal way to argue this might be to construct a recurrence function for the run time, R(n) = 1 if n R(n-1) + R(n-2) + 1 if n > 2 where R is the number of function calls. If you solve this recurrence R(n) = R(n-1) + R(n-2) + 1, you have the same general solution as the solution to f(n) = f(n-1) + f(n-2), but with a different particular solution and slightly different boundary conditions. Thus, R(n) must take the form A*phi^n + B*phihat^n + C, where A, B, and C are constant coefficients chosen to satisfy the boundary conditions. In terms of big-theta notation, this solution differs by, at most, a constant coefficient from the solution to f(n). Consequently, R = Theta(f) 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.