Google Answers Logo
View Question
 
Q: Computer Science: Complexity/Big-O Notation ( No Answer,   3 Comments )
Question  
Subject: Computer Science: Complexity/Big-O Notation
Category: Computers > Algorithms
Asked by: osakis-ga
List Price: $5.00
Posted: 05 Apr 2005 13:34 PDT
Expires: 06 Apr 2005 07:58 PDT
Question ID: 505406
In analyzing a particular algorithm, we determine that it has a complexity of 
O(n). Is it possible to also describe this algorithm as O(n^2) as well
(answer yes or no explicitly)?

If you answered "no," explain why. If you answered "yes," explain why.

If possible, please answer with your given background regarding this
field of study, and any associated literature regarding the field of
complexity, big-O notation, and any related fields.

Thanks!
Answer  
There is no answer at this time.

Comments  
Subject: Re: Computer Science: Complexity/Big-O Notation
From: bozo99-ga on 05 Apr 2005 16:40 PDT
 
Not truthfully.  If it has O(n) it does not also have O(n^2), just
like a polynomial has a term of highest order.

See for example Numerical Recipies books for a readable introduction.
Various computer science and cryptogphy books also cover it.
Subject: Re: Computer Science: Complexity/Big-O Notation
From: ramori-ga on 05 Apr 2005 22:02 PDT
 
YES 
if the running time of the program is o(n) you can say that the
running time of this algurithm is o(n^2) too
actually when you can say that the runing time of algurithm is O(n)
means that the maximun time for running is "n" times ( n is the size
of the input ) but n is the best maximum time . you can say any time
that further than "n" but "n" is the best . like 4>3 and we can say
that 7>3 and 124>3 but the best answer is 4 because 4 is the suprimum
because 4 is the minimum number that dos not further than 3 .
best regards
Subject: Re: Computer Science: Complexity/Big-O Notation
From: quadraticresidue-ga on 05 Apr 2005 23:49 PDT
 
As a tiebreaker, yes.  The definition of big-O is that the limit of
the ratio exists (is less than infinity).  If your algorithm has a
complexity of O(n), say taking time f(n) on input of size n, this
means that lim n -> infinity of f(n)/n exists.  But then lim n ->
infinity of f(n)/n^2 also exists (it will in fact be 0).  See
http://en.wikipedia.org/wiki/Big_O_notation for more information (the
second regarding "limit superior").

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