🔒 Locked

Algorithmic Order

Started by jim bob May 11, 2004 at 6:07 AM 1 replies 700+ views

Original Post

May 11, 2004 at 6:07 AM

I am having trouble determining the O-notation of an algorithm or piece of code. I can find examples of constant time O(1), linear time O(n), and quadratic time O(n^2), but I cannot find examples of the others. What are the rules for constant, linear, and quadratic time, in your own words, for clarification? And primarily... how do you determine logrithmic times O(log n), or O(n log n), how do you determine exponential O(x^n), and how do you determine factorial O(n!). Are there any others? What are the signs you are looking for, and what are the general rules in picking the order for a given code block? Also, could someone explaint the difference between little-o and big-o, and theta? Are there others? What does the phrase asymptotically bound mean in terms of these? I''ve checked every site that I can find on google, so layman descriptions are preferred, unless you think you know of the mother-of-all sites for o-notation that I probably would not have seen (first page of google or so). Thanks for any help.

ToohrVyk

May 11, 2004 at 6:19 AM

To get a polynomial-time O(n^a) complexity, just do a O(n^(a-1)) operation n times.

To get a O(log n) complexity, consider a search algorithm in a sorted array. Move to the middle of the array O(1). Now, you know which half of the array the element you''re looking for is in. Search for it in that half. O(log n) operations.

To get a O(n log n) complexity, consider the same search algorithm on a sorted list. Getting to the middle of the list now costs O(n), so the algorithm is O(n log n).

To get a O(n!) complexity, enumerate all the orders n numbers can be displayed in.

As for exponential, I don''t have one off my head right now.

What you usually do for these things is replace the algorithm you''re studying by time functions. You can call T(n) the time for that algorithm to execute on n elements, and then determine the behavior of that function when n tends to infinity.

You can say that T(n) equals the sum of the durations of the substeps of the algorithm. Such substeps may be :

- Operations the duration of which you know (looking for n-th element of a list, adding two numbers together, or an algorithm whose complexity you have already found). The time would be F(n), where F depends on the operation.

- The algorithm itself being applied recursively. The time would be T(k), where k is the number of elements it is applied on.

- An operation being repeated n times. The time is K(n)*F(n), where K(n) is the number of times the operation is repeated, and F(n) is the complexity of the operation.

Victor Nicollet, INT13 game programmer

Punty50

May 11, 2004 at 12:57 PM

To get exponential, enumerate all of the possible k-digit numbers in some particular base b. It should give you something like b^k time.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.