|
|
Subject:
DIscrete Mathematics
Category: Computers > Algorithms Asked by: alexachi-ga List Price: $2.50 |
Posted:
28 Feb 2005 19:44 PST
Expires: 30 Mar 2005 19:44 PST Question ID: 482661 |
is f(n)=O(g(n)), then g(n)= O(f(n)is true or false, give explanation? if false give counterexample? |
|
There is no answer at this time. |
|
Subject:
Re: DIscrete Mathematics
From: myoarin-ga on 01 Mar 2005 03:13 PST |
is f(n)=O(g(n)), then g(n)= O(f(n)is true or false, give explanation? False: g(n) = f(n)/O . That is, = f(n) divided by O. A quick two-fifty for a researcher. |
Subject:
Re: DIscrete Mathematics
From: mathtalk-ga on 01 Mar 2005 08:57 PST |
The "big-O" notation is used as a convenient description of the "growth" of a sequence or function, ie. the "behavior" as n tends to infinity (in the present context). Specifically, f(n) = O(g(n)) is an abbreviation for the claim that: as n --> +oo, the expression f(n)/g(n) is bounded by a fixed constant (independent of n, for all sufficiently large n) myoarin-ga is correct in saying that the assertion: f(n) = O(g(n)) implies g(n) = O(f(n)) is false, but the "division" by O is either facetious or a misunderstanding of the notation. Left as an exercise, then, is to find a counterexample, ie. sequences or functions such that f(n)/g(n) remains bounded, but g(n)/f(n) doesn't. In this respect the "big-O" notation is less precise in describing behavior of a sequence or function than the "little-o" notation. See here for definition and links to the Wikipedia article and to a contrasting definition for "little-o" notation: [big-O notation -- NIST] http://www.nist.gov/dads/HTML/bigOnotation.html regards, mathtalk-ga |
Subject:
Re: DIscrete Mathematics
From: myoarin-ga on 02 Mar 2005 03:19 PST |
Yes Sir, Mathtalk, I'll forget my highschool math and leave the answering up to you. Thanks for the clarification of what the big O means. Humbled, myoarin |
Subject:
Re: DIscrete Mathematics
From: mrx_atx-ga on 12 Mar 2005 01:06 PST |
It's false. For example log(n) is of O(n), but n is not of O(log(n)). |
If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you. |
Search Google Answers for |
Google Home - Answers FAQ - Terms of Service - Privacy Policy |