Nkruti Posted December 2, 2003 Share Posted December 2, 2003 These questions are with regard to a previous posting http://www.TestMagic.com/forum/topic.asp?TOPIC_ID=8681 What is the value of f(n) in big-O notation? function f(n) { if (n return f(n/2) + 2*f(n/4); } Should'nt the answer be O(nlogn)? ___________________________________________________ Q12) What does the following program print? int x = 1; function f(i) { int x = 2; I *= 3; for (int j = 1; j g(j); } function g(j) { print j+x; } f(x); Consider four scenarios: dynamic scope with pass-by-value, dynamic scope with pass-by-reference, static scope with pass-by-value, static scope with pass-by-reference. Dynamic scope Pass by value: 3 4 5 Pass by reference: 3 4 5 Static scope Pass by value: 2 3 4 Pass by reference: 4 5 6 _________________________________________________________ I think the answer to static scope with pass by reference should be 2 3 4 Could someone comment? Quote Link to comment Share on other sites More sharing options...
dionysus Posted December 3, 2003 Share Posted December 3, 2003 Yes, Nkruti. The answer is O(n log n). With the following explanation: f(n) = f(n/2) + 2 f(n/4) if n > 1 and is 1 if n Now, guess f(n) = c n log n + d n as the solution, which would imply that f(n) = O(n log n). Substituting, we get: c n log n + d = c (n/2) log (n/2) + d n + 2 (c (n/4) log (n/4) + d n) if N > 1 and c 1 log 1 + d 1 = d = 1 if n = 1. So therefore we get d = 1. From the first equation: c n log n + d n = c (n/2) log (n/2) + d n + c (n/2) log (n/4) + 2d n => c n log n + d n = c (n/2) (log (n/2) + log (n/4)) + 3d n => c n log n = c (n/2) log (n^2/8) + 2d n => c n log n = c (n/2) (log n^2 - log 8) + 2d n => c n log n = c n log n - c (n/2) log 8 + 2d n. Therefore, we get c (n/2) log 8 = 2d n. Putting d = 1, we have: c = 2 * 2 / log 8 = 4 / log 8 = some constant. So f(n) = O(n log n). Also, the answer of static scoping with pass by reference is indeed 4,5,6. I think you misunderstood the line I *= 3; because it really is [blue]i *= 3;[blue] To understand that, in static scoping, you can safely rename the outer x with a y. So the function body now looks like: int y = 1; function f(i) { int x = 2; i *= 3; for (int j = 1; j g(j); } function g(j) { print j+y; } f(y); Now, f(y) = f(1), so that the referenced variable I in the function f is 1, but subsequently it is multiplied by 3, so that I = 3 and therefore y = 3 since the variable is passed by reference. So calls to g as g(1), g(2), g(3) would result in 1 + 3, 2 + 3 and 3 +3 = 4, 5, 6. Which is the answer. 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.