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