View Question
 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!```
 There is no answer at this time.

 ```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.```
 ```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```
 ```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").```