Where can I find a simple introduction to the big O notation?
Q. I have just finished AS mathematics but am driven by extreme interest so am willing to learn what is required.
Asked by Jsh - Sun Jul 27 12:44:26 2008 - - 2 Answers - 0 Comments
A. Wikipedia of course . Googling it gives links such as and
Answered by nickname - Sun Jul 27 15:29:51 2008
Q. I have just finished AS mathematics but am driven by extreme interest so am willing to learn what is required.
Asked by Jsh - Sun Jul 27 12:44:26 2008 - - 2 Answers - 0 Comments
A. Wikipedia of course . Googling it gives links such as and
Answered by nickname - Sun Jul 27 15:29:51 2008
What's an easy way to understand Big-O notation?
Q. I don't get this Big-O notation stuff (I was never good with math). Is there like a quick rule of thumb to understand how to choose an algorithm based on just its Big-O notation? For example, what would be considered slow and fast in Big-O notation?
Asked by retroman - Sun Sep 24 16:08:00 2006 - - 1 Answers - 0 Comments
A. This is not entirely mathematically correct, but here goes: O(1) < O(x) < O(xlogx) < O(x^2) < ... < O (x^n) That reads algorithm of speed Big O of 1 is always faster than algorithm of speed Big O of x and algorithm of speed Big O of x is always faster than algorithm of speed Big O of xlogx and so on. The variable x stands for input size; that could be size of array, depth of a tree, population of a tree, length of a string, whatever, but it is some quantity of size not the value of input itself, a quick way of understanding O() is the extra steps that an algorithm has to go through for a growth in input size: if no extra - it is O(1) speed if growth and extra steps are proportionate - O(x) if growth:extra step ratio is xlogx - it is O(x [cont.]
Answered by Andy T - Sun Sep 24 16:24:06 2006
Q. I don't get this Big-O notation stuff (I was never good with math). Is there like a quick rule of thumb to understand how to choose an algorithm based on just its Big-O notation? For example, what would be considered slow and fast in Big-O notation?
Asked by retroman - Sun Sep 24 16:08:00 2006 - - 1 Answers - 0 Comments
A. This is not entirely mathematically correct, but here goes: O(1) < O(x) < O(xlogx) < O(x^2) < ... < O (x^n) That reads algorithm of speed Big O of 1 is always faster than algorithm of speed Big O of x and algorithm of speed Big O of x is always faster than algorithm of speed Big O of xlogx and so on. The variable x stands for input size; that could be size of array, depth of a tree, population of a tree, length of a string, whatever, but it is some quantity of size not the value of input itself, a quick way of understanding O() is the extra steps that an algorithm has to go through for a growth in input size: if no extra - it is O(1) speed if growth and extra steps are proportionate - O(x) if growth:extra step ratio is xlogx - it is O(x [cont.]
Answered by Andy T - Sun Sep 24 16:24:06 2006
What is the relationship between Big-O Notation and algorithmic efficiency? Are they related at all?
Q. In your opinion, what are the benefits of considering efficiency criteria when defining an algorithm or comparing multiple algorithms that accomplish the same tasks?
Asked by Princess - Thu Apr 5 21:18:22 2007 - - 1 Answers - 0 Comments
A. Err... more efficient algorithms tend to run faster... :) but you must be careful to consider your N. What's more efficient for large N may be less efficient for small N's (since there's setup time, for instance) as an example: for N<12, most efficient array sorting algorithm is bubble sort, although its complexity is O(N^2). if you were however to sort an array of 1,000,000 entries, O(n^2) vs. O(n logn) would make all the difference. Here's why that is: for N=4, N^2 = 16, and N logN ~ 8, so you're only saving 8 operations. Any kind of set up you have to run could easily exceed 8. for N = 1,000,000, N^2 = 10e12, and N logN ~ 2*10e7 - difference is 5 orders of magnitude! but in practice, the best approach is often measuring the… [cont.]
Answered by iluxa - Thu Apr 5 21:32:18 2007
Q. In your opinion, what are the benefits of considering efficiency criteria when defining an algorithm or comparing multiple algorithms that accomplish the same tasks?
Asked by Princess - Thu Apr 5 21:18:22 2007 - - 1 Answers - 0 Comments
A. Err... more efficient algorithms tend to run faster... :) but you must be careful to consider your N. What's more efficient for large N may be less efficient for small N's (since there's setup time, for instance) as an example: for N<12, most efficient array sorting algorithm is bubble sort, although its complexity is O(N^2). if you were however to sort an array of 1,000,000 entries, O(n^2) vs. O(n logn) would make all the difference. Here's why that is: for N=4, N^2 = 16, and N logN ~ 8, so you're only saving 8 operations. Any kind of set up you have to run could easily exceed 8. for N = 1,000,000, N^2 = 10e12, and N logN ~ 2*10e7 - difference is 5 orders of magnitude! but in practice, the best approach is often measuring the… [cont.]
Answered by iluxa - Thu Apr 5 21:32:18 2007
Can someone prove the following using the definition of big O notation?
Q. n^k is O(a^n) for all k>0, a>1.
Asked by celvin k - Tue Jul 17 02:52:44 2007 - - 1 Answers - 0 Comments
A. logn/n tends to 0 when n tends to infinity. You can get better help for your project assignment at websites like
Answered by Homework Help - Tue Jul 17 04:33:25 2007
Q. n^k is O(a^n) for all k>0, a>1.
Asked by celvin k - Tue Jul 17 02:52:44 2007 - - 1 Answers - 0 Comments
A. logn/n tends to 0 when n tends to infinity. You can get better help for your project assignment at websites like
Answered by Homework Help - Tue Jul 17 04:33:25 2007
Big O notation which math discipline is it in?
Q. i am looking for books to learn this but idk which math discipline it is in algebra???calculus?discre te math?
Asked by mercury - Thu Sep 18 15:11:53 2008 - - 1 Answers - 1 Comments
A. No idea. Look here:
Answered by jimbot - Thu Sep 18 15:15:54 2008
Q. i am looking for books to learn this but idk which math discipline it is in algebra???calculus?discre te math?
Asked by mercury - Thu Sep 18 15:11:53 2008 - - 1 Answers - 1 Comments
A. No idea. Look here:
Answered by jimbot - Thu Sep 18 15:15:54 2008
What is the Big O notation for this?
Q. What is the Big O notation form for this? 5*n^2 + n^3/2
Asked by rocafella5007 - Wed May 6 22:21:15 2009 - - 1 Answers - 0 Comments
A. O(n^3)
Answered by JoelKatz - Wed May 6 22:26:50 2009
Q. What is the Big O notation form for this? 5*n^2 + n^3/2
Asked by rocafella5007 - Wed May 6 22:21:15 2009 - - 1 Answers - 0 Comments
A. O(n^3)
Answered by JoelKatz - Wed May 6 22:26:50 2009
Big-O notation is a mathematical tool for functions like f(N) or g(N), how is it applicable to algorithm analy?
Q. Big-O notation is a mathematical tool for functions like f(N) or g(N), how is it applicable to algorithm analy?
Asked by easyd99 - Thu Jan 29 23:07:25 2009 - - 2 Answers - 0 Comments
A. Typically, N is the "size" of the input, and f(N) (or whatever) is an estimate for the amount of time it takes the algorithm to output an answer given an input of that size. For example, in computing, N can be the size of the input in bits, and f(N) can be the number of ticks of the computer's clock. One algorithm is "better" than another if one if O(f(N)) and the other is O(g(N)), where f(N) grows slower than g(N). Of course, there's an implied constant in big-O notation, so the "slower" algorithm may run faster for smaller sets of data.
Answered by John B - Thu Jan 29 23:40:10 2009
Q. Big-O notation is a mathematical tool for functions like f(N) or g(N), how is it applicable to algorithm analy?
Asked by easyd99 - Thu Jan 29 23:07:25 2009 - - 2 Answers - 0 Comments
A. Typically, N is the "size" of the input, and f(N) (or whatever) is an estimate for the amount of time it takes the algorithm to output an answer given an input of that size. For example, in computing, N can be the size of the input in bits, and f(N) can be the number of ticks of the computer's clock. One algorithm is "better" than another if one if O(f(N)) and the other is O(g(N)), where f(N) grows slower than g(N). Of course, there's an implied constant in big-O notation, so the "slower" algorithm may run faster for smaller sets of data.
Answered by John B - Thu Jan 29 23:40:10 2009
What is Big-O notation of this code?
Q. What is the big-O notation of the code following? x=something; while (x > 0) { y = y + 3; x = x / 2; { I bet this should O(log(N)) of O(N), but I am not sure. Can anybody gives me the answer and the reason for this? Thanks
Asked by Oregon S. U. 84 - Sun Sep 7 21:00:12 2008 - - 3 Answers - 0 Comments
A. I will denote f(n) (where n = 2^k) to be the number of times the division (x/2) is made, because that is the basic operation. The function's initial condition is f(1) = 1. Using backwards substitution I get: f(n) = f(n / 2^1) + 1 f(n) = f(n / 2^2) + 2, so f(n) = f(n / 2^i) + i To get to initial condition, we need (n / 2^i) to be equal to 1, so 2^i = n, and i = log2 n. f(n) = f(n / 2^(log2 n) + log2 n = f(1) + log2 n = (log2 n) + 1 So the answer is log2 n.
Answered by Ahmed The Terrorist - Sun Sep 7 21:27:06 2008
Q. What is the big-O notation of the code following? x=something; while (x > 0) { y = y + 3; x = x / 2; { I bet this should O(log(N)) of O(N), but I am not sure. Can anybody gives me the answer and the reason for this? Thanks
Asked by Oregon S. U. 84 - Sun Sep 7 21:00:12 2008 - - 3 Answers - 0 Comments
A. I will denote f(n) (where n = 2^k) to be the number of times the division (x/2) is made, because that is the basic operation. The function's initial condition is f(1) = 1. Using backwards substitution I get: f(n) = f(n / 2^1) + 1 f(n) = f(n / 2^2) + 2, so f(n) = f(n / 2^i) + i To get to initial condition, we need (n / 2^i) to be equal to 1, so 2^i = n, and i = log2 n. f(n) = f(n / 2^(log2 n) + log2 n = f(1) + log2 n = (log2 n) + 1 So the answer is log2 n.
Answered by Ahmed The Terrorist - Sun Sep 7 21:27:06 2008
Big O notation. Need help to explain the answers from the book?
Q. Hi, im having some problems understanding big o notation. My professor did a 1 day review, and our text book offers a 2 page blurp about it. However she has given us an assignment with a few questions on it(im not looking for answers to my homework, im simply wanting someone to explain the examples from my book) but i simply do not understand what to do to solve these problems, or what exactly they mean by their answers. Ill list a couple of examples from my book and hope you guys can help me understand what exactly is going on. This useless peice of junk that i wasted money on likes to simply give me the example and answer with no reasoning inbetween: Examp: 3logn + 2 is O(log n) Answer: <= 5log n for n >=1 Examp: 2n + 100log n is O(n)… [cont.]
Asked by Adam B - Fri Sep 19 21:17:54 2008 - - 2 Answers - 0 Comments
A. First of all, I would really advise you to get a better book, or try to find a better explanation on the web. - my personal recommendation. I will try to explain Big-O as simple as I can, but it is far from enough, you must find a resource for the study. Big-O simply shows how fast your algorithm will grow as you give it more input. It ignores the constants because it takes a limit as n -> infinity, in which case constants get dropped. So something like 5n^2 - 1 is O(n^2) Whenever you have function consisting of multiple variables with different orders of magnitude, you only take the one that is of higher order! That is why 3n^2 + n - 5 is O(n^2) - n is of lower magnitude so drop it! That is why in your 2n + 100log n is O(n), logs… [cont.]
Answered by Ahmed The Ninja - Fri Sep 19 22:15:55 2008
Q. Hi, im having some problems understanding big o notation. My professor did a 1 day review, and our text book offers a 2 page blurp about it. However she has given us an assignment with a few questions on it(im not looking for answers to my homework, im simply wanting someone to explain the examples from my book) but i simply do not understand what to do to solve these problems, or what exactly they mean by their answers. Ill list a couple of examples from my book and hope you guys can help me understand what exactly is going on. This useless peice of junk that i wasted money on likes to simply give me the example and answer with no reasoning inbetween: Examp: 3logn + 2 is O(log n) Answer: <= 5log n for n >=1 Examp: 2n + 100log n is O(n)… [cont.]
Asked by Adam B - Fri Sep 19 21:17:54 2008 - - 2 Answers - 0 Comments
A. First of all, I would really advise you to get a better book, or try to find a better explanation on the web. - my personal recommendation. I will try to explain Big-O as simple as I can, but it is far from enough, you must find a resource for the study. Big-O simply shows how fast your algorithm will grow as you give it more input. It ignores the constants because it takes a limit as n -> infinity, in which case constants get dropped. So something like 5n^2 - 1 is O(n^2) Whenever you have function consisting of multiple variables with different orders of magnitude, you only take the one that is of higher order! That is why 3n^2 + n - 5 is O(n^2) - n is of lower magnitude so drop it! That is why in your 2n + 100log n is O(n), logs… [cont.]
Answered by Ahmed The Ninja - Fri Sep 19 22:15:55 2008
what is big O and omega notation in C language?
Q. this is related to complexity. i want to know more about it but in short so as in oral answer
Asked by asn - Sun Oct 25 14:52:50 2009 - - 1 Answers - 0 Comments
Q. this is related to complexity. i want to know more about it but in short so as in oral answer
Asked by asn - Sun Oct 25 14:52:50 2009 - - 1 Answers - 0 Comments
How do you solve for/get Big O Notation?
Q. All the questions here are about what Big O Notation is (mostly people too lazy to do their own homework). I have an honor's project looking into the speed of certain algorithms and my teacher said to look into "Big O Notation". I read and understood what it is. But how do you get it? Do you just look at a code and say "Oh this is O(n^2)." ? Or do you have to test it with various values for n? All the books im looking at tell me what Big O means and what it does in terms of f(x) and g(x). I'm lost.
Asked by winnydamarpoe - Tue Oct 20 14:12:49 2009 - - 2 Answers - 0 Comments
A. "Do you just look at a code and say "Oh this is O(n^2)." ?" With experience, you do. Big O notation becomes useful when processing lots of things, because this is where algorithms break down and can become slow as n gets larger. You always devise the worst case scenario for Big O notation, so while you might search an array for a value and find it on the first try, it's still O(N) because in the worst case, you wouldn't find the value until you reached the end. Rarely will you write code to determine Big O notation, a simple description of the algorithm or some source code should be enough to determine the order of the algorithm. Their are generally two types of order, exponential and logarithmic. Exponential occurs with nested loops, [cont.]
Answered by Pfo - Tue Oct 20 15:58:30 2009
Q. All the questions here are about what Big O Notation is (mostly people too lazy to do their own homework). I have an honor's project looking into the speed of certain algorithms and my teacher said to look into "Big O Notation". I read and understood what it is. But how do you get it? Do you just look at a code and say "Oh this is O(n^2)." ? Or do you have to test it with various values for n? All the books im looking at tell me what Big O means and what it does in terms of f(x) and g(x). I'm lost.
Asked by winnydamarpoe - Tue Oct 20 14:12:49 2009 - - 2 Answers - 0 Comments
A. "Do you just look at a code and say "Oh this is O(n^2)." ?" With experience, you do. Big O notation becomes useful when processing lots of things, because this is where algorithms break down and can become slow as n gets larger. You always devise the worst case scenario for Big O notation, so while you might search an array for a value and find it on the first try, it's still O(N) because in the worst case, you wouldn't find the value until you reached the end. Rarely will you write code to determine Big O notation, a simple description of the algorithm or some source code should be enough to determine the order of the algorithm. Their are generally two types of order, exponential and logarithmic. Exponential occurs with nested loops, [cont.]
Answered by Pfo - Tue Oct 20 15:58:30 2009
Big Omega and Big O Notation question?
Q. If f(n) is OMEGA(n) and g(n) is O(n^2). How do I show which of the following are true? f(n) is O(n) f(n) is OMEGA(1) f(n) is O(n^2) g(n) is OMEGA (n) Thanks for any help.
Asked by heater2 - Thu Nov 5 10:37:12 2009 - - 1 Answers - 0 Comments
A. f(n) is OMEGA(n) <==> There exists C > 0 such that |f(n)| >= Cn for sufficiently large n. g(n) is O(n^2) <==> There exists D > 0 such that |g(n)| <= Cn^2 for sufficiently large n. --- Since |f(n)| >= Cn >= C * 1 for sufficiently large n, we see that f(n) is OMEGA(1). The others are likely false, since the inequalities are facing the wrong directions. Counterexamples: f(n) = n^3 is OMEGA(n) (by taking C = 1), but n^3 is neither O(n) nor O(n^2), since it grows faster than either set. g(n) = 1 is O(n^2) (by taking D = 1), but 1 is not OMEGA(n) since n grows while n does not. I hope this helps!
Answered by kb - Thu Nov 5 12:49:45 2009
Q. If f(n) is OMEGA(n) and g(n) is O(n^2). How do I show which of the following are true? f(n) is O(n) f(n) is OMEGA(1) f(n) is O(n^2) g(n) is OMEGA (n) Thanks for any help.
Asked by heater2 - Thu Nov 5 10:37:12 2009 - - 1 Answers - 0 Comments
A. f(n) is OMEGA(n) <==> There exists C > 0 such that |f(n)| >= Cn for sufficiently large n. g(n) is O(n^2) <==> There exists D > 0 such that |g(n)| <= Cn^2 for sufficiently large n. --- Since |f(n)| >= Cn >= C * 1 for sufficiently large n, we see that f(n) is OMEGA(1). The others are likely false, since the inequalities are facing the wrong directions. Counterexamples: f(n) = n^3 is OMEGA(n) (by taking C = 1), but n^3 is neither O(n) nor O(n^2), since it grows faster than either set. g(n) = 1 is O(n^2) (by taking D = 1), but 1 is not OMEGA(n) since n grows while n does not. I hope this helps!
Answered by kb - Thu Nov 5 12:49:45 2009
What is meant by the (runtime) order of an algorithm (big- O notation?
Q. What is meant by the (runtime) order of an algorithm (big- O notation?
Asked by William.J T - Sun Jan 14 12:06:16 2007 - - 2 Answers - 0 Comments
A. Good luck doing your homework!
Answered by jacovkss2 - Sun Jan 14 12:43:05 2007
Q. What is meant by the (runtime) order of an algorithm (big- O notation?
Asked by William.J T - Sun Jan 14 12:06:16 2007 - - 2 Answers - 0 Comments
A. Good luck doing your homework!
Answered by jacovkss2 - Sun Jan 14 12:43:05 2007
Big O notation?
Q. int value = n, count = 0; while (value > 1){ value = value /2; count++; } What is the big O?
Asked by waffleironmanboy - Thu Sep 20 23:54:08 2007 - - 1 Answers - 0 Comments
A. O(logn), more precisely this takes log base 2 of n steps, because the is the number of time you can divide n in half until you get less than 1.
Answered by Phineas Bogg - Fri Sep 21 00:56:53 2007
Q. int value = n, count = 0; while (value > 1){ value = value /2; count++; } What is the big O?
Asked by waffleironmanboy - Thu Sep 20 23:54:08 2007 - - 1 Answers - 0 Comments
A. O(logn), more precisely this takes log base 2 of n steps, because the is the number of time you can divide n in half until you get less than 1.
Answered by Phineas Bogg - Fri Sep 21 00:56:53 2007
Big O Notation Help?
Q. Can anyone help me with this problem and explain a little more about the omega, theta, and Big O? Thanks! In each of the following situations, please indicate whether f=O(g), or f= (g), or both (in which case f=Q (g).) f(n) g(n) a. n-100 n-200 b. n^(1/2) n^(2/3) c. 100n+log n n +(log n)^2 d. nlogn 10nlogn e. log2n log3n f. 10logn log(n^2) g. n^1.01 nlog^2n h. n^2/logn n(logn)^2 i. n^0.1 (logn)^10 j. (logn)^logn n/logn Thanks!
Asked by Moto - Tue Aug 26 23:07:03 2008 - - 2 Answers - 0 Comments
A. I think it is A, but it has been a long time since I have dealt with Big-O notation... so my answers and explanations may be off... but I think they are good. Anyways, Big O is the upper bound. So something like O(n^2) is saying that your algorithm is going to be in or less than some constant multiplied by n^2. Also, when dealing with polynomials, generally the part that has the largest impact as n approaches infinity matters. So something like 6x^4 + 3x^2 + 4 would be O(x^4). Also, if I remember correctly, because O() is considered to be an upper bound, you could put the 6x^4 + 3x^2 + 4 function under O(x^8) because it would still be under that upper bound...even though that upper bound isn't nearly as precise as they would want it. If… [cont.]
Answered by Me M - Tue Aug 26 23:57:16 2008
Q. Can anyone help me with this problem and explain a little more about the omega, theta, and Big O? Thanks! In each of the following situations, please indicate whether f=O(g), or f= (g), or both (in which case f=Q (g).) f(n) g(n) a. n-100 n-200 b. n^(1/2) n^(2/3) c. 100n+log n n +(log n)^2 d. nlogn 10nlogn e. log2n log3n f. 10logn log(n^2) g. n^1.01 nlog^2n h. n^2/logn n(logn)^2 i. n^0.1 (logn)^10 j. (logn)^logn n/logn Thanks!
Asked by Moto - Tue Aug 26 23:07:03 2008 - - 2 Answers - 0 Comments
A. I think it is A, but it has been a long time since I have dealt with Big-O notation... so my answers and explanations may be off... but I think they are good. Anyways, Big O is the upper bound. So something like O(n^2) is saying that your algorithm is going to be in or less than some constant multiplied by n^2. Also, when dealing with polynomials, generally the part that has the largest impact as n approaches infinity matters. So something like 6x^4 + 3x^2 + 4 would be O(x^4). Also, if I remember correctly, because O() is considered to be an upper bound, you could put the 6x^4 + 3x^2 + 4 function under O(x^8) because it would still be under that upper bound...even though that upper bound isn't nearly as precise as they would want it. If… [cont.]
Answered by Me M - Tue Aug 26 23:57:16 2008
big o notation code analysis
Q. hey can you help me find the big O w..for the worst case for the followwing code for (int i=1; i<=n; i ) { if (i==n/2) { for (int j= 0; j>=n*n) { System.out.println("hi") } } } and why to loren. never assume. not a class assignment acutally.. im studying for an exam. and this was on a previous exam. just asking for help thats all, a little stressed here so you obviously, shouldnt assume
Asked by dtigers - Wed Aug 6 21:53:56 2008 - - 1 Answers - 0 Comments
A. This is obviously a class assignment so I'm not simply going to give an answer. The first step to solving something like this is to reformat the code with indentation to show what is dependent on what. You have two loops and one conditional. How many times does the outer loop execute? Of these, how many times does it actually execute the inner loop? When the inner loop executes, how many times does it call the final line you're trying to measure?
Answered by Loren Pechtel - Wed Aug 6 23:04:33 2008
Q. hey can you help me find the big O w..for the worst case for the followwing code for (int i=1; i<=n; i ) { if (i==n/2) { for (int j= 0; j>=n*n) { System.out.println("hi") } } } and why to loren. never assume. not a class assignment acutally.. im studying for an exam. and this was on a previous exam. just asking for help thats all, a little stressed here so you obviously, shouldnt assume
Asked by dtigers - Wed Aug 6 21:53:56 2008 - - 1 Answers - 0 Comments
A. This is obviously a class assignment so I'm not simply going to give an answer. The first step to solving something like this is to reformat the code with indentation to show what is dependent on what. You have two loops and one conditional. How many times does the outer loop execute? Of these, how many times does it actually execute the inner loop? When the inner loop executes, how many times does it call the final line you're trying to measure?
Answered by Loren Pechtel - Wed Aug 6 23:04:33 2008
What is the time complexity (Big-O notation) of a Binomial Queue? of a Btree?
Q. What is the time complexity (Big-O notation) of a Binomial Queue? of a Btree?
Asked by Rwar - Wed Nov 7 03:49:52 2007 - - 1 Answers - 0 Comments
A. time complexity is exponential
Answered by timo - Wed Nov 7 03:55:13 2007
Q. What is the time complexity (Big-O notation) of a Binomial Queue? of a Btree?
Asked by Rwar - Wed Nov 7 03:49:52 2007 - - 1 Answers - 0 Comments
A. time complexity is exponential
Answered by timo - Wed Nov 7 03:55:13 2007
Big O notation proof help?
Q. 1. Show that log base 10(x) is O(log base 2(x)) 2. Show that log(x^2 + 1) is O(log base 2(x)) 3. Show that 3x + 7 is O(x)
Asked by geeeee - Fri Aug 21 19:54:04 2009 - - 2 Answers - 0 Comments
A. log{base a} x = log{base b} x / log{base b } a for #1. [3x+7] < 4x for x > 7 for #3. for #2 use log{base 10} [ x +1] / log {base 2} x = log{base2} [x +1] / ( [ log {base2} 10][log {base2} x] ) < log{base2} [x + 1] / 3log{base2} x = log{base2} [x +1] / log{base2} x^3 < 1 when x > 2 don't ask for more work as you are supposed to do the proofs...I just gave you the basic ideas to use
Answered by ted s - Fri Aug 21 20:22:00 2009
Q. 1. Show that log base 10(x) is O(log base 2(x)) 2. Show that log(x^2 + 1) is O(log base 2(x)) 3. Show that 3x + 7 is O(x)
Asked by geeeee - Fri Aug 21 19:54:04 2009 - - 2 Answers - 0 Comments
A. log{base a} x = log{base b} x / log{base b } a for #1. [3x+7] < 4x for x > 7 for #3. for #2 use log{base 10} [ x +1] / log {base 2} x = log{base2} [x +1] / ( [ log {base2} 10][log {base2} x] ) < log{base2} [x + 1] / 3log{base2} x = log{base2} [x +1] / log{base2} x^3 < 1 when x > 2 don't ask for more work as you are supposed to do the proofs...I just gave you the basic ideas to use
Answered by ted s - Fri Aug 21 20:22:00 2009
Landau's big O notation. math expert help please!?
Q. the question is too complicated to type so it is in this link. please show how you do this. thanks
Asked by robinsonscott95 - Tue Sep 30 23:09:34 2008 - - 1 Answers - 0 Comments
A. Maybe something like this: numerator is x^2 + O(x^3) denominator is (-1/2) x^2 + O(x^4), so quotient is -2 + O(x), so limit is -2.
Answered by JB - Wed Oct 1 00:12:51 2008
Q. the question is too complicated to type so it is in this link. please show how you do this. thanks
Asked by robinsonscott95 - Tue Sep 30 23:09:34 2008 - - 1 Answers - 0 Comments
A. Maybe something like this: numerator is x^2 + O(x^3) denominator is (-1/2) x^2 + O(x^4), so quotient is -2 + O(x), so limit is -2.
Answered by JB - Wed Oct 1 00:12:51 2008
Faulty Big O notation proof?
Q. Given that f(n) = O(g(n)), prove that 2^f(n) = O(2^g(n)), or provide a counterexample if false. f(n) = O(g(n)) f(n) <= cg(n) 2^f(n) <= 2^(cg(n)) 2^f(n) <= 2^c * 2^g(n) 2^f(n) <= c' * 2^g(n) where c' = 2^c 2^f(n) = O(2^g(n)) My TA told me that 2^f(n) = O(2^g(n)) is false. Can someone point out the error of this proof, and possibly provde a counterexample to disprove this statement?
Asked by thebeatboxguy - Sun Sep 6 15:38:41 2009 - - 1 Answers - 0 Comments
A. Where are the absolute value signs? f(n) = O(g(n)) means |f(n)| <= c |g(n)| for some c > 0 and sufficiently large n. Counterexample: Let f(n) = n and g(n) = - n^2. So, |n| <= 1 * |-n^2| = n^2 for all n >= 1 (with c = 1) ==> f(n) = O(g(n)). However, 2^f(n) = 2^n and 2^g(n) = 2^(-n^2). Since 2^n --> infinity while 2^(-n^2) --> 0 as n--> infinity, it is impossible for 2^f(n) = O(2^g(n)). I hope that helps!
Answered by kb - Sun Sep 6 16:10:28 2009
Q. Given that f(n) = O(g(n)), prove that 2^f(n) = O(2^g(n)), or provide a counterexample if false. f(n) = O(g(n)) f(n) <= cg(n) 2^f(n) <= 2^(cg(n)) 2^f(n) <= 2^c * 2^g(n) 2^f(n) <= c' * 2^g(n) where c' = 2^c 2^f(n) = O(2^g(n)) My TA told me that 2^f(n) = O(2^g(n)) is false. Can someone point out the error of this proof, and possibly provde a counterexample to disprove this statement?
Asked by thebeatboxguy - Sun Sep 6 15:38:41 2009 - - 1 Answers - 0 Comments
A. Where are the absolute value signs? f(n) = O(g(n)) means |f(n)| <= c |g(n)| for some c > 0 and sufficiently large n. Counterexample: Let f(n) = n and g(n) = - n^2. So, |n| <= 1 * |-n^2| = n^2 for all n >= 1 (with c = 1) ==> f(n) = O(g(n)). However, 2^f(n) = 2^n and 2^g(n) = 2^(-n^2). Since 2^n --> infinity while 2^(-n^2) --> 0 as n--> infinity, it is impossible for 2^f(n) = O(2^g(n)). I hope that helps!
Answered by kb - Sun Sep 6 16:10:28 2009
From Yahoo Answer Search: 'Big O notation'
Fri Nov 20 00:28:12 2009 [ refresh local cache ]
[Hide]▼
news.google.com
Reuters
O ) is pitching to five of the world's biggest advertising companies a deal to buy Razorfish, its digital ad agency, The Wall Street Journal reported on ...
and more »
netcrema.com
delicious
hu, 09 Jul 2009 20:55:03 GM
Plain English Explanation of . Big O. Notationcforcoding.com.
[Hide]▲
