Google Answers Logo
View Question
 
Q: DIscrete Mathematics ( No Answer,   4 Comments )
Question  
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?
Answer  
There is no answer at this time.

Comments  
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)).

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

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 Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy