iankelling.org Git - iankelling.org/blob - blog/2014-09-29-say-on2.md

   1 ---
   2 title:  "Say O(n²) Eighty Eight Times Fast"
   3 comment_links:
   4   reddit: https://www.reddit.com/r/programming/comments/2hth4h/say_on%C2%B2_eighty_eight_times_fast/
   5   hacker news: https://news.ycombinator.com/item?id=8384945
   6 ---
   7
   8 The symbol `<` is spoken "less than", but how did you know that? Unfortunately, it's common practice for documentation and educational material to teach words and symbols without an adequate explanation of how to say them. And often, googling it doesn't work.
   9
  10 Why does it matter? Of course for communicating, but also for your own skill and understanding. When you read, you still think the word verbally, so you would end up choosing a word like "left angle bracket" which is less intuitive, and probably leaves a lingering sense of uncertainty about it. Yuck.
  11
  12 Separately, some technical terms have multiple equivalent spoken variations and which one is best to use when and why is an unsolvable mystery. One such case is the verbal equivalent of [Big O notation](https://en.wikipedia.org/wiki/Big_O_notation) (update: what I mean here is not strictly big o notation, but the language around it for computer science context). I've done a few interviews recently, and I noticed that my interviewers used a variety of terms, and my own phrasing has awkwardly shifted around too. Maybe we can figure something out together:
  13
  14
  15 <div>
  16 <button onclick="nextWord()">How to talk about O(n²) in conversation?</button><br><br>
  17
  18 <p id="demo">"__________________"</p><br>
  19 Vote: <button onclick="yesVote()">It sounds good</button> <button onclick="mehVote()">It sounds ok</button>
  20 <button onclick="noVote()">It sounds wrong or confusing</button>
  21
  22
  23 <script>
  24 // @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&dn=gpl-2.0.txt GPLv2.0 or later
  25 var words = [
  26 "asymtotic bound of n squared",
  27 "asymtotic bound n squared",
  28 "asymtotic run time of n squared",
  29 "asymtotic run time n squared",
  30 "asymtotic growth of n squared",
  31 "asymtotic growth n squared",
  32 "asymtotic growth rate of n squared",
  33 "asymtotic growth rate n squared",
  34 "bound of n squared",
  35 "bound n squared",
  36 "run time of n squared",
  37 "run time n squared",
  38 "growth of n squared",
  39 "growth n squared",
  40 "growth rate of n squared",
  41 "growth rate n squared",
  42 "computational complexity of n squared",
  43 "computational complexity n squared",
  44 "computational efficiency of n squared",
  45 "computational efficiency n squared",
  46 "computational growth rate of n squared",
  47 "computational growth rate n squared",
  48 "big oh complexity of n squared",
  49 "big oh complexity n squared",
  50 "big oh efficiency of n squared",
  51 "big oh efficiency n squared",
  52 "big oh growth rate of n squared",
  53 "big oh growth rate n squared",
  54 "algorithmic complexity of n squared",
  55 "algorithmic complexity n squared",
  56 "algorithmic efficiency of n squared",
  57 "algorithmic efficiency n squared",
  58 "algorithmic growth rate of n squared",
  59 "algorithmic growth rate n squared",
  60 "time complexity of n squared",
  61 "time complexity n squared",
  62 "time efficiency of n squared",
  63 "time efficiency n squared",
  64 "time growth rate of n squared",
  65 "time growth rate n squared",
  66 "asymtotic complexity of n squared",
  67 "asymtotic complexity n squared",
  68 "asymtotic efficiency of n squared",
  69 "asymtotic efficiency n squared",
  70 "asymtotic growth rate of n squared",
  71 "asymtotic growth rate n squared",
  72 "complexity of n squared",
  73 "complexity n squared",
  74 "efficiency of n squared",
  75 "efficiency n squared",
  76 "growth rate of n squared",
  77 "growth rate n squared",
  78 "big oh of n squared",
  79 "big oh n squared",
  80 "order of n squared",
  81 "order n squared",
  82 "order of complexity of n squared",
  83 "order of complexity n squared",
  84 "time of n squared",
  85 "time n squared",
  86 "quadratic asymtotic bound",
  87 "quadratic asymtotic run time",
  88 "quadratic asymtotic growth",
  89 "quadratic asymtotic growth rate",
  90 "quadratic bound",
  91 "quadratic run time",
  92 "quadratic growth",
  93 "quadratic growth rate",
  94 "quadratic computational complexity",
  95 "quadratic computational efficiency",
  96 "quadratic computational growth rate",
  97 "quadratic big oh complexity",
  98 "quadratic big oh efficiency",
  99 "quadratic big oh growth rate",
 100 "quadratic algorithmic complexity",
 101 "quadratic algorithmic efficiency",
 102 "quadratic algorithmic growth rate",
 103 "quadratic time complexity",
 104 "quadratic time efficiency",
 105 "quadratic time growth rate",
 106 "quadratic asymtotic complexity",
 107 "quadratic asymtotic efficiency",
 108 "quadratic asymtotic growth rate",
 109 "quadratic complexity",
 110 "quadratic efficiency",
 111 "quadratic growth rate",
 112 "quadratic big oh",
 113 "quadratic order",
 114 "quadratic order of complexity",
 115 "quadratic time",
 116 "oh n squared",
 117 "oh of n squared"];
 118
 119 function yesVote() {
 120     nextWord("yes")
 121 }
 122 function mehVote() {
 123     nextWord("meh")
 124 }
 125 function noVote() {
 126     nextWord("bad")
 127 }
 128
 129 word = "The end."
 130 function nextWord(vote) {
 131     if ('undefined' !== typeof vote) {
 132         var xmlhttp = new XMLHttpRequest();
 133         xmlhttp.open("POST","/On2voting.py",true);
 134         xmlhttp.setRequestHeader("Content-Type", "application/json;charset=UTF-8");
 135         xmlhttp.send(JSON.stringify({vote:vote, word:word}));
 136     }
 137     word = "The end."
 138     if (words.length >= 1) {
 139         wordIndex = Math.floor(Math.random() * words.length)
 140         word = words[wordIndex];
 141     }
 142     document.getElementById("demo").innerHTML = '"' + word + '"';
 143     words.splice(wordIndex, 1)
 144
 145 };
 146 // @license-end
 147 </script>
 148 </div>
 149 My next blog post [has the results](/blog/on2-vote-results.html).
 150
 151 Where did I get these terms? Just a few clicks around the internet and my own experience. I started idly writing a few, which started to become a [Backus–Naur Form (BNF)](https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form). Then I got quite annoyed that I couldn't figure out how to properly pronounce Naur. Turns out it's [like now-ah](http://forvo.com/search/naur/). Then I wrote a python program which expands the BNF to all possible combinations:
 152
 153 ~~~ py
 154 from itertools import product
 155
 156 def bnf_expand(*args):
 157     result = []
 158     for arg in args:
 159         result.extend([" ".join(filter(None, x)) for x in product(*arg)])
 160     return result
 161
 162 # the BNF in reverse of normal order
 163 asymtotic = ['asymtotic', '']
 164 asymtotic_modified = ['bound', 'run time', 'growth', 'growth rate']
 165 commonly_modified = ['complexity', 'efficiency', 'growth rate']
 166 common_modifiers = ['computational', 'big oh', 'algorithmic', 'time',
 167                      'asymtotic', '']
 168 unmodified = ['big oh', 'order', 'order of complexity', 'time']
 169 O = bnf_expand([asymtotic, asymtotic_modified],
 170                 [common_modifiers, commonly_modified], [unmodified])
 171 of = ['of', '']
 172 On2 = bnf_expand([O, of, ["n squared"]], [['quadratic'], O],
 173                  [['oh n squared']], [['oh of n squared']])
 174
 175 # Print the top level expanded BNF
 176 print On2
 177 ~~~
 178
 179 The result is 92 terms which can work the same in a conversation (unless your votes/comments say otherwise). And that doesn't even consider whether to say someting _is_ O(n²), _has_ O(n²), or _is of_ O(n²).
 180
 181 The list is a bit long, so I put them in javascript and made some buttons.
 182
 183 You might call all these words "terms of art", or "jargon", or "lingo"... orrr, let's call the whole thing off.