Newsgroups: comp.os.msdos.djgpp From: "A. Jans-Beken" Subject: Re: The meaning of O(n)... Content-Type: text/plain; charset=us-ascii Message-ID: <34C5BF2B.1159@oce.nl> Sender: news AT oce DOT nl (The Daily News @ nntp01.oce.nl) Content-Transfer-Encoding: 7bit Organization: Océ-Nederland B.V. References: Mime-Version: 1.0 Date: Wed, 21 Jan 1998 09:26:03 GMT Lines: 53 To: djgpp AT delorie DOT com DJ-Gateway: from newsgroup comp.os.msdos.djgpp Precedence: bulk Gili wrote: > > Hi, > > I have noticed that lots algorithms provide their efficency as O(n), > where N is the number of elements they are operating on. The last math > course I have taken is Calculus 2 and I do not recall ever seeing the > O(n) function. What does it mean? How efficient is something with > O(n)? Thanks in advanced, > > Gili In an array or list 'N' represents the number of elements. For example: int x[100] has 100 elements. O(n) means that an algorithm takes some time that is constant for each element. Hence the processing time of the complete array/list depends only on the number of elements in it. For example: for (int i = 0; i < 100; i++) cout << x[i]; has an efficiency of O(n). O(n^2) means that an algorithm takes some time proportional to the number of elements TO THE POWER OF TWO which is a very bad efficiency for large number of elements. For example: for (int i = 0; i < 100; i++) for (int j = 0; j < 100; j++) cout << x[i] << "-" << x[j]; has an efficiency of O(n^2). Very efficient algorithms may be of efficiency O(log N). Think of binary search trees for example. In such an algorithm NOT EVERY ELEMENT must be checked and the complexity is therfore LESS than N. Final note: When in a loop you must perform 2 operations on each element than the efficiency is O(2n). Altough it is less efficient then O(n) it is common practice to say that O(2n) is the same order of efficiency as O(n). For example: O(100) = 100 operations for the algorithm. O(2.100) = 200 operations for the algorithm. O(100^2) = 10000 operations for the algorithm. O(log 100) = 2 operations for the algorithm. It is clear that a log algorithm is preferred when possible (altough software is commonly more complex to write).