O

The "O", in Pittsburgh is the Original Hot Dog Shop, famous for its really fried fries, the too big pizzas and the ultraburp hamburghers.

The place has now a franchise on the CMU campus, and the food has not gotten any lighter for the academic environment.

1. Jeux D'Eau
2. Mer Noire
3. Tzelma
4. Africa
5. Remous
6. Remous
7. Svecounia
8. Nostalgie
9. Simcha
10. Gamelan
11. Ephra
12. Désert
13. Terre Aride
14. O

big-O: O(...)

The theoretical upper limit of execution time (complexity) of an algorithm given the problem size n.

quicksort runs in O(n log n) time. bubble sort runs in O(n²). To sort 1,000,000 numbers, quicksort will take about 6,000,000 steps, while bubble sort will take 1,000,000,000,000.

The ideal algorithm is O(1), which means that it takes a constant time to run regardless of the size of the data structure. An example of O(1) is insertion of a node to the start of a linked list. Hashtable lookups run in O(1).

The next best thing is O(log N), which grows slowly as the data set gets larger. The increase of 1,000 to 1,000,000 items is only a 2x increase in run time. Examples of O(log N) are searches on sorted data structures and operations on binary trees.

O(N) are very common. These algorithms take proportional time to the size of the data. Examples include appending to the end of a linked list, or searching an unsorted data structure.

O(N Log N) are the better sorting algorithms. Quicksort and Mergesort are examples. Most algorithms that take a 'divide and conquer' strategy are O(N Log N).

O(N²) begins the downward trend. With the data set going from 1,000 to 1,000,000 elements, it takes 1,000,000 times as long to complete. The slower sorting algorithms are O(N²), insert sort and select sort.

O(N³) and above are never to be used except in an emergency. Even worse are algorithms with non-polynomial complexity such as O(2^N). Most O(2^N) are brute force, badly designed, or implementing a problem that is inherently very slow. To go from a data set of 1 to 1,000 results in 2⁹⁹ times more operations, or about 10³⁰⁰. Also avoid O(N!) algorithms.

m_turner says in the preceding node:

"big-O: O(...)
The theoretical upper limit of execution time (complexity) of an algorithm given the problem size n."
yada yada yada
"To go from a data set of 1 to 1,000 results in 299 times more operations, or about 10300. Also avoid O(N!) algorithms."

Oh you crazy techies!!

The "Big O" is an orgasm.

Perhaps a term more commonly used by females, who perhaps are more inclined to euphemisms....

Perhaps.

The letter O is often used when signing correspondence to indicate a hug. Thus signing a letter with XOX would indicate that you are sending the reader "hugs and kisses". The O likely represents the circle formed by a person's arms when hugging someone else.

O, along with X, is also regularly used in the game of noughts and crosses otherwise known as tic-tac-toe.

It is an open debate whether these two uses have anything relation, but the coincidence is quite suggestive.

O (oh).

1.

O, the fifteenth letter of the English alphabet, derives its form, value, and name from the Greek O, through the Latin. The letter came into the Greek from the Phœnician, which possibly derived it ultimately from the Egyptian. Etymologically, the letter o is most closely related to a, e, and u; as in E. bone, AS. ban; E. stone, AS. stan; E. broke, AS. brecan to break; E. bore, AS. beran to bear; E. dove, AS. dūfe; E. toft, tuft; tone, tune; number, F. nombre.

The letter o has several vowel sounds, the principal of which are its long sound, as in bone, its short sound, as in nod, and the sounds heard in the words orb, son, do (feod), and wolf (book). In connection with the other vowels it forms several digraphs and diphthongs. See Guide to Pronunciation, §§ 107-129.

2.

Among the ancients, O was a mark of triple time, from the notion that the ternary, or number 3, is the most perfect of numbers, and properly expressed by a circle, the most perfect figure.

O was also anciently used to represent 11: with a dash over it (Ō), 11,000.

© Webster 1913.

O (oh), n.; pl. O's ∨ Oes ().

1.

The letter O, or its sound.

Tennyson.

2.

Something shaped like the letter O; a circle or oval.

Shak.

3.

A cipher; zero.

Thou art an O without a figure. Shak.

© Webster 1913.

O (oh), a. [See One.]

One.

© Webster 1913.

O (oh), interj.

An exclamation used in calling or directly addressing a person or personified object; also, as an emotional or impassioned exclamation expressing pain, grief, surprise, desire, fear, etc.

For ever, O Lord, thy word is settled in heaven. Ps. cxix. 89.

O how love I thy law ! it is my meditation all the day. Ps. cxix. 97.

⇒ O is frequently followed by an ellipsis and that, an in expressing a wish: "O [I wish] that Ishmael might live before thee !" Gen. xvii. 18; or in expressions of surprise, indignation, or regret: "O [it is sad] that such eyes should e'er meet other object !"

Sheridan Knowles.

⇒ A distinction between the use of O and oh is insisted upon by some, namely, that O should be used only in direct address to a person or personified object, and should never be followed by the exclamation point, while Oh (or oh) should be used in exclamations where no direct appeal or address to an object is made, and may be followed by the exclamation point or not, according to the nature or construction of the sentence. Some insist that oh should be used only as an interjection expressing strong feeling. The form O, however, is, it seems, the one most commonly employed for both uses by modern writers and correctors for the press. "O, I am slain !" Shak. "O what a fair and ministering angel !" "O sweet angel !" Longfellow.

O for a kindling touch from that pure flame ! Wordsworth.

But she is in her grave, -- and oh The difference to me ! Wordsworth.

Oh for a lodge in some vast wilderness ! Cowper.

We should distinguish between the sign of the vocative and the emotional interjection, writing O for the former, and oh for the latter. Earle.

O dear, ∧ O dear me! [corrupted fr. F. O Dieu! or It. O Dio! O God! O Dio mio! O my God! Wyman], exclamations expressive of various emotions, but usually promoted by surprise, consternation, grief, pain, etc.

© Webster 1913.