

Subject:
Computer Science: Complexity/BigO Notation
Category: Computers > Algorithms Asked by: osakisga 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, bigO notation, and any related fields. Thanks! 

There is no answer at this time. 

Subject:
Re: Computer Science: Complexity/BigO Notation
From: bozo99ga 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/BigO Notation
From: ramoriga 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/BigO Notation
From: quadraticresiduega on 05 Apr 2005 23:49 PDT 
As a tiebreaker, yes. The definition of bigO 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"). 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 