The origin of the symbol Θ (big theta) in asymptotic notation

& (verbiage overflow) ⋅ ⋅ Tue 10 April 2012 ⋅ RSS ⋅ Search ⋅ Subscribe

In a recent review of Roger Hart's superb Chinese Roots of Linear Algebra (2010) I've described what I believe is the motivation of Donald Knuth's symbol Θ ("big theta") in asymptotic notation.

I think it is a graphic pun on the O ("big O") that stands for German Ordnung 'order', as in "order of growth". I suggest that the bar in the middle of Θ is intended to represent tight bounds above and below, in contrast to big O (upper bound) and big omega (lower bound). I have not seen this explanation anywhere else.

Hart's book is presently described on the Johns Hopkins University Press site, though such listings tend not to be permanent. The Project MUSE page for his book is at https://muse.jhu.edu/books/9780801899584.

For more on Hart's research, see his website, http://rhart.org/.

[end]

All articles

  1. John Holt's Instead of Education (1976)
  2. John Holt on learning in mid-life and the role of the teacher (1978)
  3. What goes in a README?
  4. Self-segregation
  5. Python decorators for object-oriented method behaviors
  6. The English Level of This Year's Principal Presidential Candidates
  7. Chao on Wenyan
  8. Face 面子
  9. Some Questions about the Recurse Center
  10. De-duplicate Apple Calendars on Mavericks
  11. Transcribing Voice Recordings on OS X, 3 — another example
  12. Transcribing Voice Recordings on OS X, 2 — more examples
  13. Transcribing Voice Recordings on OS X
  14. Interview with Rachel Vincent
  15. The Pre-Morse Origin of Two Morse Code Symbols
  16. “The Man Who Knew Infinity” — 2015 movie about Ramanujan
  17. Why does Python have two ways to filter a comprehension?
  18. There is no ternary operator in Python
  19. Does Fortran have a two-way decision function?
  20. Debugging the Art Museum
  21. Learning to Throw Books Away
  22. About Me
  23. Walter Murch on Standing at Work
  24. “Our Kind of Story”
  25. Revisiting the Taiwan national anthem
  26. Review of Button, Phonetic Ambiguity in the Chinese Script
  27. Importing Modules under Pytest
  28. Two Git Accounts on One Computer
  29. Pytest parametrization — passing multiple data-items to a single test
  30. Markdown Basic References
  31. Two Curious Things about screen.width and screen.height on Mobile Firefox and under iOS.
  32. Where Do I Stand on Digital Advertising?
  33. Progressing to the Next Level after Two Years at Hacker School
  34. Health Insurance $5,600/year ⇨ $12,600/year to Keep Our Doctor
  35. Always Use Dry-run Options If Possible
  36. Basic Interaction with Man-pages
  37. Taiwanese Cantillation Prosody and the Standard Tradition of Regulated Verse
  38. Automated Transcription of a Lyric’s Melody
  39. Quote-Unquote: Quick Python Conversion to and from URI Standard Format
  40. Literate Code in Crista Lopes’s Exercises in Programming Style
  41. Special Computer Help for an Uncooperative Person in Need
  42. Richard Bellman on Multistage Decision Processes
  43. Contradictory Advice from Kenkō about Studying after Mid-life
  44. Deceit for my Mother’s Sake
  45. New York State’s Law on Intercoms
  46. Our Relationship with Unwelcome Callers
  47. Reasons to Keep a Landline Phone
  48. Chinese (Pinyin) Tone Marks on Macintosh
  49. Suicide by Holding the Breath in the Greek Classics
  50. Transcribing a Solo Voice Recording to Western Musical Notation
  51. Surprise Text Message Sent by Google Voice
  52. Trimming a Git Repo before Moving It to GitHub
  53. The Sage Chilōn on Gesticulation
  54. Examining the Identity of a “Whole-Sliced” Python Sequence
  55. Pagerank after Completing the Move of My Blog
  56. Haydn on Originality
  57. Stages of Life
  58. Linguistic Naturalism in Behavior-Driven Development
  59. Some Advice on Interviewing in China
  60. The AARP on Ageism
  61. The Cash Value of a Lost Moment
  62. How Did 釁 Get Into My Computer? A Talk at CSTUY
  63. I Knock My Head on the Ground: Review of Richter, Letters and Epistolary Culture in Early Medieval China
  64. Two Pair of Suspenders Back to Amazon
  65. Knuth on the Direction of the Tree in Computer Science
  66. Py3K Versions of Networking Programs for the Rhodes and Goerzen Book
  67. A Fake Monk in Times Square
  68. Werner Herzog on the jungle’s “articulate obscenity”, “misery”, and “sort of harmony of collective murder”
  69. Hacker School and How we Learn
  70. Hacker School Sees “The Internet’s Own Boy”
  71. Two Chinese manifestations of black cardamom
  72. A natural-language URL shortener
  73. Recovering Web and Search visibility after Leaving WordPress
  74. Greedy evaluation in Python's default dictionary
  75. Trying to Change Google Pagerank after Moving my Blog
  76. Ensuring my blog is indexed by Google, using Webmaster Tools
  77. 'Dependency' in programming means the opposite of its traditional meaning
  78. Experimenting with a Site-Analytics Tracker
  79. Unexpected Behavior from the Python 3 Built-In Hash Function
  80. Rote learning and programming
  81. r0ml on the workspace-based, image-oriented programming paradigm
  82. In technology, knowing your vulnerabilities is a desirable strength
  83. The Lingering Puzzle of yán 焉
  84. My grandmother’s diaries
  85. Scholarly Presentation: Arousing something other than polite interest
  86. Friedrich Gulda's Beethoven
  87. Reaction to Jaron Lanier Talk at Cooper Union
  88. Yuen Ren Chao on Chanting Chinese Poetry
  89. The legal requirement of having a camera inside a NYC taxicab
  90. This blog has moved
  91. "Web of Trust" in Chinese and Japanese
  92. Taking the larger view of frustrations with technology
  93. Reflecting on Bernard Baruch, on the need for character and thinking
  94. Dinner with a Bletchley Park cryptographer
  95. Karl Popper on conflict between your basic assumptions and those of your interlocutor (1965)
  96. My Hacker School Pairing Interview
  97. Thirty political parties fielding candidates in New York City this election
  98. The world's only speaker of standard Mandarin in 1923
  99. Data within literal curly brackets using Python format()
  100. The Imperative Style in Commits and Docstrings
  101. Git overwrites file metadata including creation and modification date
  102. Two complaints and one word of praise about GitHub Flavored Markdown
  103. Lǐ Bái on time (8th century)
  104. Two bits of trivia from the Institute for Advanced Study
  105. Karl Popper against foundations of knowledge (1965)
  106. George Orwell on falsification of fact (1946)
  107. Loss of innocence for "ggg"
  108. George Orwell against uniformity of political principles (1946)
  109. Library technology at the Institute for Advanced Study
  110. Richard Feynman on scientific integrity (1974)
  111. Richard Feynman on ignorance of science (1964)
  112. Tense in Git Commit Messages
  113. A better plan is needed for transporting equipment in the subway
  114. "Premature optimization" as phrased by Musashi
  115. Finding and returning zero or one of a marked sub-expression in Python regex
  116. A faster Python sort
  117. A question about time complexity when testing membership in a Python nested sequence
  118. Rendering a matrix as a linear array
  119. Attempting a generic SQL INSERT statement in Python
  120. Welsh bwg 'bogey': an alternate proposal about the origin of "computer bug"
  121. Using python str.format(*args) when the cardinality of *args is unknown
  122. Compelled by forces I can no longer resist…
  123. Highlights of the July, 2013, NY Tech Meetup
  124. Review of Zádrapa posted
  125. Now filtering (> /dev/null) some spam before it reaches the Gmail Spam folder
  126. Isaac Newton, creationist
  127. Freeman-Halton 3x3 exact test
  128. Conjure me: reentering the zone of proximal development
  129. Python extend() without a list comprehension
  130. The name "Hacker School"
  131. The benefits of Hacker School
  132. Another two subway rules of thumb illustrated
  133. Short-circuiting and (and ==) instead of if in Python
  134. Quintilian on time and study
  135. Kenkō on time and study
  136. George Orwell on keeping a diary to cultivate dispassionate thinking
  137. A bon mot of Quintilian on theory
  138. Growth of outlook at Hacker School
  139. Nakamoto Satoshi, the name of Bitcoin's inventor
  140. The psychology of pairing and code review at Hacker School
  141. Computer science and rugelach
  142. Is Hacker School like graduate school?
  143. Why do I work so hard at Hacker School?
  144. Hacker School compared with studying computer science at City College
  145. Differences between code and natural language
  146. Hacker School after six weeks
  147. Pairing at Hacker School
  148. The Norman Manchu dictionary has reached Seattle
  149. Jerry Norman's Manchu dictionary has appeared
  150. Two things I am thinking about as Hacker School begins
  151. The white powder on the pages of library books
  152. Non-math uses of LaTeX
  153. Hacker School
  154. Hacker School (dojo/recruiter for programmers) begins in four days
  155. Dependencies for scipy and matplotlib not handled by pip
  156. The National Do Not Call Registry no longer works well
  157. Early evidence of a dislike of Christmas music?
  158. Plinyesque Christmas wishes to all
  159. Getting the Android GridView sample code to work
  160. A small triumph of explicitly readable code
  161. Godfrey Reggio on technology in life (2002)
  162. Max Weber: "science is the affair of an intellectual aristocracy" (1918)
  163. First day of Android coding: two problems solved
  164. Black optimism explained
  165. Talking across the pre- and post-computer border
  166. Getting used to the disappearance of old institutional models
  167. Anything less than perfect is a failing grade
  168. Recovering from hurricane Sandy
  169. Max Weber on meritocracy in academia (1918)
  170. Our state of things in New York right now (after hurricane Sandy)
  171. Max Weber on the "strange intoxication" of a passionate vocational devotion (1918)
  172. LaTeX's extract package, used for isolating the contents of environments and commands
  173. Fellini movie "Broadway Bomb" being filmed in my neighborhood
  174. Does Apple view an "iPhone" phone number as something different from a "mobile" phone number?
  175. Columbia University Libraries finally removing the card catalog
  176. One more rule of thumb for the New York subway
  177. Two further rules of thumb for the New York subway
  178. Two inches taller in two years
  179. Alternate ways to say "pop" and "push" in computer science
  180. Poulenc's Dialogues des Carmélites at the Dell' Arte Opera Ensemble
  181. Andrew Nathan on Doh Chull Shin on Confucianism and Democratization (2012)
  182. Proofreading poorly OCRed material
  183. New York State redistricting maps on line at CUNY's Center for Urban Research
  184. Karl Berry on free software (2005)
  185. The SEC on the utility of Python as a secure and accessible tool for generating official reports (2010)
  186. Hill Country
  187. Yogurt whey-starter pickled (soured) mackerel
  188. Images (figures) on facing pages in a LaTeX document
  189. Just what is being centrally limited in the "Central Limit Theorem"?
  190. Reloading modified code when using the Ipython interactive shell
  191. Alistair Cooke on H. L. Mencken's typing (1956, 1977)
  192. Jerry Norman (1936–2012)
  193. Ptisan issues
  194. Elia Kazan on the need for selfishness
  195. "Neither side took prisoners" — Japanese and American atrocities in the Pacific theater of World War II
  196. Surprise! You have a different Congressman now but no one thought you needed to know.
  197. Another notice of the bureaucratization of academia
  198. Bogusław Jackowski on "worldwide licensing madness" (2008)
  199. Accommodating the Chinese hunger for official seals on official documents.
  200. Bond Street and a story about a smartphone
  201. Another bond to Apple is lost as MobileMe Sync is discontinued
  202. Charles Ives (1874–1954) on his life in business (1933)
  203. "Taikonaut" and the new Cold War
  204. James Lang on improving understanding and retention by increasing "cognitive disfluency" (2012)
  205. Lǔ Xùn 魯迅 (1881–1936) on the truth behind Confucian morality (1918)
  206. Ray Bradbury (1920–2012) on cars (1963)
  207. Ray Bradbury (1920–2012) on success in the arts (1963)
  208. Chinatown breakfast offerings
  209. Zed Shaw on why to use C (2011)
  210. A step in my Chinese education
  211. Age and the MBA
  212. Useful Python time formats for dealing with HTTP headers
  213. An encounter with Google's security rules
  214. HTML headers for keeping track of updated webpages
  215. William Hung 洪業 (1893–1980) on Confucianism (1980)
  216. David Daniels on one's "other voice" (1998)
  217. Elia Kazan and questions of betrayal
  218. Advice on preparing herring
  219. Two limitations of call-forwarding on Google Voice
  220. Student protests in Montréal and thoughts about tuition
  221. Call-screening in Google Voice has a problem
  222. Cortlandt Alley's Chinese name
  223. Chinatown shorthand
  224. "Download statusbar" add-on for Firefox
  225. The ceremonial gateways of Montréal's Chinatown
  226. Nailset = chasse-clou
  227. Restaurant Mai Xiang Yuan [Màixiāngyuán cānguǎn 麥香園餐館] in Montréal
  228. A bon mot of Peter Carey about reviews of one's work (2012)
  229. A bon mot of Peter Carey about New York (2012)
  230. Identifying the active bridge adapter for use with a headless virtual machine on VirtualBox
  231. Doubts about l'affaire Chén Guāngchéng 陳光誠
  232. Military officers who cannot count
  233. Parallel text and vocabulary in LaTeX
  234. A stricture on Google Voice
  235. Resolving VirtualBox error VERR_INTNET_FLT_IF_NOT_FOUND
  236. Ubuntu 12.04LTS (Precise Pangolin) on VirtualBox
  237. Recordings for Classical Chinese
  238. Arthur Luehrmann on "computer literacy" (1972)
  239. The origin of the symbol Θ (big theta) in asymptotic notation
  240. Being censored in China
  241. The experience of learning vim commands
  242. How should I rate this movie on Netflix?
  243. Netflix miscalculation — Hugo
  244. Curious vim behavior: treats date range as subtraction
  245. Alexandra Lord on the myth of the academic career (2012)
  246. Elia Kazan on getting along in society (1974)
  247. ssh unavailable over Amtrak's wifi network
  248. Tricked again by Python's mutable objects
  249. Is blocking ads theft of service?
  250. A poor analogy on intellectual property rights
  251. A mutton chop at Keen's Steakhouse
  252. An anecdote about William Hung (Hóng Yè 洪業, 1893-1980)
  253. Sorting a list of Unicode strings in Python, case-insensitively and ignoring diacritics
  254. Avoid deleting the contents of a file in Python through sloppy use of "write" mode
  255. Reloading a Python module after modifying it
  256. Frank Mittelbach on documentation (2006)
  257. Frank Mittelbach on collaboration (2006)
  258. Frank Mittelbach's "moral obligation" license for the LaTeX multicol package
  259. Keith Whalen records scales and patterns from the Slonimsky Thesaurus
  260. Calligraphy in Chinatown
  261. Manchu dictionary done
  262. Bernard Shaw (1856–1950) on the damage done by immaturity in politics
  263. Gotham breakneck to Chinatown
  264. Calculus III progresses
  265. Some Western recipe-names as transformed by the Taiwanese linguistic experience
  266. Class war against the banking and financial industry
  267. Avoiding the Emailyama
  268. Adblock Plus is the most useful piece of shareware I've ever had
  269. A less painful way to install Adblock Plus filter-subscriptions in Firefox
  270. Tales from Calculus III
  271. Jack Cheng on "the technology I grew up with" (2012)
  272. Distribution of fonts: competing models are coexisting
  273. MoinMoin for notebook-wiki (and WordPress, you are trying the patience of my affections)
  274. generate native MATLAB code from finished figures, for study
  275. Quintilian on laziness and difficulty in one's studies
  276. Guide to Gwoyeu Romatzyh 國語羅馬字 (tonal spelling for Mandarin)
  277. Guide to the radicals of the traditional Chinese dictionary
  278. Origins of the Mandarin Phonetic Symbols (注音符號/ㄅㄆㄇㄈ)
  279. Installing UCC certificate for multiple domain names hosted virtually on a single server
  280. QuickTime Pro easily concatenates .m4v video files
  281. Columbia to Chinatown walk, 20120122
  282. A local custom without the corresponding exotic saying in rural Taiwan
  283. HTTPS being rejected at Yahoo hosting
  284. Classical Chinese syllabus posted; using Landslide for markdown-to-HTML5
  285. Phonosymbolism, etymology, and the nebulous Chinese word family
  286. Simple meal at Shui Mei Café (嘎嘎叫, 67A East Broadway, NYC), formerly So Go Café)
  287. Are cell phones and bananas radioactive?
  288. LaTeX and electronic documents
  289. New definition of “algorithm”
  290. Materials used in paper bank statements
  291. Finally making progress with Vim
  292. Kenneth S. Wherry on American influence in China (1940)
  293. Propagation of a meme and a metameme
  294. Against the single time zone
  295. Hamish Milne on transcriptions of Bach (2005)
  296. Choosing a suitable site for fieldwork, and working with illiterate informants in China
  297. Yuen Ren Chao (1892–1982) urging Americans to resist Chinese telephantasmia (1921)
  298. The brown German flour of Przasnysz
  299. Recollection of the traditional bagel in central Poland before World War I
  300. Vaclav Havel (1936–2011) on doing good work (1978)
  301. Vaclav Havel (1936–2011) on the "dictatorship of technology" (1978)
  302. Vaclav Havel (1936–2011) on ideological enslavement (1978)
  303. Vaclav Havel (1936–2011) on law (1978)
  304. Vaclav Havel (1936–2011) on responsibility and a "post-democratic" system (1978)
  305. Vaclav Havel (1936–2011) on "opposition" and "dissident" (1978)
  306. Vaclav Havel (1936–2011) on ideology (1978)
  307. 'Factorial' in Chinese (jiēchéng 階乘/阶乘)
  308. Leibniz’s theodicy, dynamic programming, and strategies for learning
  309. Emanuel Derman and Paul Wilmott on mathematical models and self-delusion (2009)
  310. Y. R. Chao and Henry Sheffer added to the Mathematics Genealogy Project
  311. Two more rules of thumb for the New York subway
  312. Math in the Movies
  313. Jim Coplien on reflection and problem-solving (2011)
  314. Richard Feynman on practical applications of the theory of gravitation (1964)
  315. Karl Popper on understanding a problem (1963)
  316. Galileo on "reason conquering sense" (1632)
  317. Apparent error in Python's priority queue and heapq
  318. Literacy book finally out
  319. Y. R. Chao on his dissertation (1974)
  320. Doctoral pedigrees
  321. Lack of stable sort in Python's priority queue
  322. Suitable pots for making turmeric tea
  323. Neuro-plasticity and strategies for improving cognitive functioning: "The Brain Fitness Program" (2007)
  324. Code-switching between comfortable cognitive aptitudes and the main aptitudes used in math and coding
  325. Wishes for the Orthodox Nativity Season (began 15 November this year)
  326. Two rules of thumb about transportation in New York
  327. Pípá yā 琵琶鴨 (Frisbee Duck)
  328. Testing the reliability of the Python priority queue
  329. Edsger Dijkstra on programming as an intellectual discipline (2001)
  330. Edsger Dijkstra on the name of the field Computer Science (2001)
  331. Edsger Dijkstra on anthropomorphizing computers (2001)
  332. Edsger Dijkstra on mastery of one's native tongue as a vital programming skill (2001)
  333. Edsger Dijkstra on the origin of his shortest path algorithm (2001)
  334. Efrem Podgaits's New York Mass (2001)
  335. Anecdotal report on experimenting with creatine as a study aid
  336. "Suppose" for math proofs, in LaTeX
  337. A rule of thumb in teaching
  338. Graphing flowcharts and automata in LaTeX
  339. Perception of time and suspension of finality (studying math)
  340. Suddenly perceiving the cantus firmus in a Bach chorus
  341. Two of Elvira's arias from Don Giovanni
  342. Identifying robots among human beings
  343. Apparent misspelling in LaTeX command set: \guillemotleft and \guillemotright
  344. Table of contents in a LaTeX book: make the TOC entry different from the actual chapter headings in the text
  345. Competition and sharing in academia
  346. Kuhn and Popper
  347. Herb Gross's calculus lectures
  348. The abbreviation UTC as an acronym
  349. Clyde Haberman on validating one's authenticity as a New Yorker (2011)
  350. The era of lost words
  351. Never odd or even
  352. William Deresiewicz on multitasking and solitude (2009)
  353. Bjarne Stroustrup's advice to up-and-coming programmers (2008)
  354. Chet Ramey's advice to up-and-coming programmers (2008)
  355. Bjarne Stroustrup on the name C++ and common criticisms of the language
  356. Steve Bourne, advice to up-and-coming programmers (2009)
  357. Alfred Aho on the origins of awk (2008)
  358. Leslie Lamport on thinking first and on commenting code (2007)
  359. Pens of choice for linguistic fieldwork
  360. How I learned LaTeX
  361. Some bons mots from Edsger Dijkstra (1984)
  362. Non-paean to Steve Jobs
  363. Annotations of Cormen et al.'s algorithm for a Red-Black Tree (delete and delete-fixup functions only)
  364. John McCarthy on "Generality in Artificial Intelligence" (1987)
  365. Brian Kernighan's summary thoughts on scripting languages
  366. Changes to the inventory of IPython magic commands (v. 0.10 to 0.11)
  367. One man's calm reflection on Java-think in Python
  368. mdfind as a substitute for locate on Mac OS X
  369. Reconsider P. T. Barnum's reputation
  370. LaTeX macro for circling answers on math problem sets
  371. View of the Mariana Trench
  372. Simulating private variables in Python
  373. Choice of formats for basic code documentation
  374. Dennis Ritchie on Computer Science and Commerce (1984)
  375. Inconsistent results of the same seed in random.seed() on different Python installations
  376. An opinion on vi configuration
  377. The virtue of Vim (or: why I do not remap copy and paste)
  378. Shark fin and the economics of Chinese "face"
  379. Two funerary practices and the end of a good story
  380. An important skill for instructors
  381. p::c
  382. Twice-a-day mail delivery
  383. Portmanteau characters in Chinese (abstract)
  384. A math professor I enjoyed
  385. The state of my Netflix patronage
  386. Longevity vs. versatility of code
  387. A new kind of noise in the subway
  388. Router VI is dead
  389. Tinker Tailor remake
  390. Automated upward pricing spiral
  391. Break-in?
  392. Telephantasmia, one of the great gifts of Chinese culture
  393. September 11th sensations
  394. Whether to take a small loss or consent to the devaluation of the US dollar
  395. City checkpoint chaos
  396. Continuing opportunity for techno-elitism
  397. A worry of Donald Knuth's
  398. An opinion of TeX
  399. Advice on teaching English in China if you lack a TEFL degree
  400. "The Highline" Park
  401. Plutarch on the sensitivity and versatility of the human mind
  402. Plutarch's praise of the "fox" temperament
  403. Unagi hitsumabushi 鰻櫃まぶし
  404. My mother and me, at work on the Early China index, 20110526
  405. juémíngzǐ 決明子 tisane
  406. Brillat-Savarin on the pleasures of the fast
  407. University of Maryland, (College Park) general education rated D in a national survey
  408. The EMACS meta key and the standing desk
  409. A rule of thumb in choosing one's tools
  410. Dr. Johnson on the "fox" temperament
  411. Carl Elliott reviews Ginsberg, Fall of the Faculty (WSJ)
  412. Hard copy vs. electronic copy
  413. Deborah Ball's article on the opposition to standardizing the Romansh language (WSJ)
  414. Boris Veytsman's review of Kottwitz, LaTeX Beginner's Guide
  415. Why even 212 phone numbers calling in-area have to dial 212 first
  416. Dr. Johnson on keeping a diary
  417. Against object-oriented design (except in scripting languages)
  418. Worrying about inadequate memory to hold program and debugger (1973)
  419. Consequences of a compiler defect
  420. The Internet and scripting languages
  421. Newton's own suffering at math
  422. Fresh turmeric-root tea
  423. Appreciation of awk
  424. "Computer Science, Modern Languages Most Gender-Polarized Majors"
  425. Food issues during the Siege of Leningrad
  426. Starting a blog