nonevent99 Posted October 31, 2003 Share Posted October 31, 2003 Given each function below, express the function in big-O notation. If you're feeling really zealous, find the running time in big-O notation, too. If you're feeling positively exuberant, find closed form solutions, too. function f(n) { if (n return f(n/2) + 1; } function g(n) { if (n return 10*g(n/10) + 10; } function h(n) { if (n return h(n/2) + h(n/4); } function i(n) { if (n return i(n-2); } function j(n) { if (n return j(n-2) + j(n-1); } function k(n) { if (n return k(n/2) + n * lg(n); } function l(n) { if (n return l(n/4) + n^7; } Quote Link to comment Share on other sites More sharing options...
wood Posted October 31, 2003 Share Posted October 31, 2003 function f(n) { if (n return f(n/2) + 1; } f(n) = O(1) + O(logN) = O(logN) function g(n) { if (n return 10*g(n/10) + 10; } g(n) = O(10^log10 N) + O([10^[(log10 N) + 1] - 1] / 9) = O(10^log10 N) = O(n) I'll get to the rest later. Wood Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted October 31, 2003 Author Share Posted October 31, 2003 I think your answer for g is right, g(n) approx = n/5. I'm not so sure about f. Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted October 31, 2003 Share Posted October 31, 2003 function f(n) { if (n return f(n/2) + 1; } [color=Red]f(n) = O(log(n))[/color] function g(n) { if (n return 10*g(n/10) + 10; } [color=Red]g(n) = O(log(n))[/color] function h(n) { if (n return h(n/2) + h(n/4); } [color=Red]h(n) = O(nlog(n))[/color] function i(n) { if (n return i(n-2); } [color=Red]i(n) = O(n)[/color] function j(n) { if (n return j(n-2) + j(n-1); } [color=Red]j(n) = O(2^(n-4))[/color] function k(n) { if (n return k(n/2) + n * lg(n); } [color=Red]k(n) = O(log(n))[/color] function l(n) { if (n return l(n/4) + n^7; } [color=Red]l(n) = O(log(n))[/color] I kind of doubt that you wanted those results. A more interesting problem would be what's returned by the above functions? That would be equivalent to solving some recurrence equations. Given each function below, express the function in big-O notation. If you're feeling really zealous, find the running time in big-O notation, too., What do you mean by that, isn't big-O notation used for the time complexity of algos? What do you mean by first sentence? Quote Link to comment Share on other sites More sharing options...
wood Posted November 1, 2003 Share Posted November 1, 2003 AlbaLed, can you explain your answer to this question? function g(n) { if (n return 10*g(n/10) + 10; } (1) g(n) = 10*g(n/10)+10 (2) = 10*(10*g(n/100)+10)+10 (3) = 10*(10*(10*g(n/1000)+10)+10)+10 ... (log10(n)) = 10^(log10(n)-1) + 10^(log10(n)-1)+10^(log10(n)-2)+...+10 = n/10 + [10^(log10(n) - 10] / 9 = n/10 + (n - 10)/9 = O(n) Am I missing something? I double checked by running the C fragment and it looks definitely linear... Thanks, Wood Quote Link to comment Share on other sites More sharing options...
rafi_dery Posted November 1, 2003 Share Posted November 1, 2003 Wood: I think AlbaLed refered to the running time of the functions. AlbaLed: about h: why is it O(nlogn) and not O(n)? Quote Link to comment Share on other sites More sharing options...
The_Wonderful_Vipul Posted November 1, 2003 Share Posted November 1, 2003 Originally posted by nonevent99 Given each function below, express the function in big-O notation. If you're feeling really zealous, find the running time in big-O notation, too. If you're feeling positively exuberant, find closed form solutions, too. function f(n) { if (n return f(n/2) + 1; } [/quote] [color=Red] O(log(n)) [/color] [quote] function g(n) { if (n return 10*g(n/10) + 10; } [/quote] [color=Red] O(n) [/color] [quote] function h(n) { if (n return h(n/2) + h(n/4); } [/quote] [color=Red] O(lg(n)^2) [/color] [quote] function i(n) { if (n return i(n-2); } [/quote] [color=Red] O(n) [/color] [quote] function j(n) { if (n return j(n-2) + j(n-1); } [/quote] [color=Red] O(2^n) [/color] [quote] function k(n) { if (n return k(n/2) + n * lg(n); } [/quote] [color=Red] O(nlog(n)) [/color] [quote] function l(n) { if (n return l(n/4) + n^7; } [/quote] [color=Red] O(n^7) [/color] Quote Link to comment Share on other sites More sharing options...
wood Posted November 1, 2003 Share Posted November 1, 2003 Originally posted by rafi_dery Wood: I think AlbaLed refered to the running time of the functions. AlbaLed: about h: why is it O(nlogn) and not O(n)? Rafi: I didn't understand what you meant by that. I am also refering to the running time of the functions. What would be the other interpretation? Quote Link to comment Share on other sites More sharing options...
wood Posted November 1, 2003 Share Posted November 1, 2003 function j(n) { if (n return j(n-2) + j(n-1); } [color=Red]j(n) = O(2^(n-4))[/color] That looks like fib series. However, recursion should stop at j(4) or below. So, the recursion is 2^k f(n-2k) and considering n-2k = 4, k = (n-4)/2, so the recursion is O(2^[(n-4)/2]) to be precise and not 2^(n-4), right? Please, let me know. Wood Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 1, 2003 Share Posted November 1, 2003 [/size]Originally posted by wood AlbaLed, can you explain your answer to this question? function g(n) { if (n return 10*g(n/10) + 10; } (1) g(n) = 10*g(n/10)+10 (2) = 10*(10*g(n/100)+10)+10 (3) = 10*(10*(10*g(n/1000)+10)+10)+10 ... (log10(n)) = 10^(log10(n)-1) + 10^(log10(n)-1)+10^(log10(n)-2)+...+10 = n/10 + [10^(log10(n) - 10] / 9 = n/10 + (n - 10)/9 = O(n) Am I missing something? I double checked by running the C fragment and it looks definitely linear... Thanks, Wood[/size] Wood you're finding what the program returns not the running time, big-O, that's why I said it could have be good if the quest asked for what's returned too. Quote Link to comment Share on other sites More sharing options...
wood Posted November 1, 2003 Share Posted November 1, 2003 Ops... got it... stupid mistake. Wood Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 1, 2003 Share Posted November 1, 2003 rafi_dery, thanks for pointing it out, I think you're right Here is the idea h(n) = h(n/2) + h(n/4) so the value & complexity of this function should be the number of leaves on a binary tree with n nodes. or 2^(hght-1) hght = log(n) 2^(log(n)-1) = O(n) thnx Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 1, 2003 Author Share Posted November 1, 2003 Ok, guys, here are the answers I got. They augment what you all wrote above, and in at least one case contradict your answers. Maybe we can hash the differences out... Given each function below, express the function in big-O notation. If you're feeling really zealous, find the running time in big-O notation, too. If you're feeling positively exuberant, find closed form solutions, too. f(n) = f(n/2)+1 f(n) = O(lg(n)) {master theorem} run time = O(lg(n)) {n divided by 2 per iteration} g(n) = 10*g(n/10)+10 g(n) = O(n) {master theorem} run time = O(log n) {n divided by 10 per iteration} h(n) = h(n/2) + h(n/4) h(n) = O(n) {writing them out thru n=128} run time = O(lg n) {n dividied by at least 2 per iteration) i(n) = i(n-2); i(n) = n when n i(n) = 2 - n%2 {writing a few out} run time = O(n) {n reduced by 2 per iteration} j(n) = j(n-2) + j(n-1) j(n) = O(phi^n) {Fibonnaci sequence} run time = O(phi^n); phi = (1+sqrt5)/2 k(n) = k(n/2) + nlgn k(n) = O(nlgn) {Master theorem} run time = O(lg n) {n divided by 2 per iteration} l(n) = l(n/4) + n^7 l(n) = O(n^7) {Master theorem} run time = O(log n base 4) {n divided by 4 per iteration} Fun? Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 1, 2003 Share Posted November 1, 2003 lots of it !!!! You've got more ??? Good job nonevent Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 1, 2003 Share Posted November 1, 2003 nonevent are you sure about h, I am getting something different for the run time, check my last post Quote Link to comment Share on other sites More sharing options...
wood Posted November 1, 2003 Share Posted November 1, 2003 I agree... it should be O(n). Wood Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 2, 2003 Author Share Posted November 2, 2003 Originally posted by AlbaLed nonevent are you sure about h, I am getting something different for the run time, check my last post Yeah, I think the run time will be more than O(lg n) for h(n). My bad. It's definitely bounded above by 2*R(n/2), since R(n/2) > R(n/4) (R = run time), which is to say bounded above by R(n). The actual R(n) = R(n/2) + R(n/4) + 1. This turns out to be another situation like in the other thread http://www.TestMagic.com/forum/topic.asp?TOPIC_ID=8612 where it would be O(n) if we were doing 2*R(n/2), but since we aren't quite adding R(n/2) each time, it's still O(n^p) but p In this case, it appears that a good p is 0.7. SO the runtime is O(n^p) for h. This is very interesting. Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 2, 2003 Share Posted November 2, 2003 nonevent, if you want a really tight tight tight tight tight bound I thin you've got to be looking at n^(log4(3)) = O(n^0.79). How did you get 0.7?? Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 2, 2003 Author Share Posted November 2, 2003 Originally posted by AlbaLed nonevent, if you want a really tight tight tight tight tight bound I thin you've got to be looking at n^(log4(3)) = O(n^0.79). How did you get 0.7?? Experimentation. I could have made a mistake. But it looks like 0.7 works. Here's the code I used: <br /> function R(n) {<br /> if (n <= 1) return 1;<br /> return R(n/2) + R(n/4)+1;<br /> }<br /> <br /> <br /> document.write("<table>");<br /> for (var n = 1; n < 1000000; n *= 2) {<br /> var x = R(n);<br /> document.write("<tr><td>"+n+" <td>"+x+" <td>"+x/Math.pow(n,0.7));<br /> }<br /> document.write("");<br /> <br /> Quote Link to comment Share on other sites More sharing options...
iamdaisy Posted October 30, 2007 Share Posted October 30, 2007 Ok, guys, here are the answers I got. They augment what you all wrote above, and in at least one case contradict your answers. Maybe we can hash the differences out... f(n) = f(n/2)+1 f(n) = O(lg(n)) {master theorem} run time = O(lg(n)) {n divided by 2 per iteration} g(n) = 10*g(n/10)+10 g(n) = O(n) {master theorem} run time = O(log n) {n divided by 10 per iteration} h(n) = h(n/2) + h(n/4) h(n) = O(n) {writing them out thru n=128} run time = O(lg n) {n dividied by at least 2 per iteration) i(n) = i(n-2); i(n) = n when n i(n) = 2 - n%2 {writing a few out} run time = O(n) {n reduced by 2 per iteration} j(n) = j(n-2) + j(n-1) j(n) = O(phi^n) {Fibonnaci sequence} run time = O(phi^n); phi = (1+sqrt5)/2 k(n) = k(n/2) + nlgn k(n) = O(nlgn) {Master theorem} run time = O(lg n) {n divided by 2 per iteration} l(n) = l(n/4) + n^7 l(n) = O(n^7) {Master theorem} run time = O(log n base 4) {n divided by 4 per iteration} Fun? Why there are two different O-notations : for function and runtime?? Isnot the O-notation for a function is for it's run time resource usage and space usage?? and we generally talk about run time (as space is not much an issue) Please help me as I might be loosing some serious concept.. Quote Link to comment Share on other sites More sharing options...
CalmLogic Posted October 30, 2007 Share Posted October 30, 2007 I'm not the best at explaining this, but, basically: Run-time complexity relates to execution time. Function complexity relates to the growth of a fuction ("order of growth"). The way I grasped this concept intuitively was just looking at examples in discrete math books, ETS sample questions, examples in this forum, etc. Quote Link to comment Share on other sites More sharing options...
taro_curly Posted October 30, 2007 Share Posted October 30, 2007 The O notation is an order of growth notation. It helps you to concisely represent how fast a function will "grow" w.r.t. some input. Therefore, when you say that the order of growth of a function is f(n) is O(n), what you are saying is that as n increases, f(n) will increase linearly. A crude way of putting it would be, if the order of growth is O(n^2), then f(n) is proportional to n^2 i.e. f(n) = kn^2 When you are talking about the order of growth of a function f, you are talking about the magnitude of the function. Let us say that the time to required f for input n is given by f_t(n) Whereas, when you are talking about the growth of the running time, you are talking about f_t grows with n. Hope this makes sense... Quote Link to comment Share on other sites More sharing options...
iamdaisy Posted October 31, 2007 Share Posted October 31, 2007 Calmlogic and taro_curly, thank you so much for this explanation ------------- :) daisy 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.