輸入大小（input size）
當我們說一個演算法跑在 O(n^2) 時間裡，那個 n 默默承擔了很多工作，值得追問一句：n 是什麼的 n？輸入大小就是我們拿來衡量成本的那個數。可以把它想成問題裝進來的那只盒子有多大：更長的字串、更大的清單、有更多道路的圖。誠實的慣例是：數一數把輸入寫到機器紙帶上需要多少個符號，所以 n 是編碼後輸入的長度，而不是某種「這問題感覺多複雜」的非正式概念。
選對 n 是陳述問題的一部分。對排序任務，n 通常是清單裡的項目個數。對圖問題，我們常用 n 表示頂點數、m 表示邊數，並回報像 O(n + m) 這樣的時間。對單一個數字像「N 是質數嗎？」，微妙之處便顯現：N 本身可以大得驚人，但你只用約 log N 個二進位數字就能寫下它，所以輸入大小大約是 log N，而非 N。一個對大小 n = log N 的輸入要跑 N 步的演算法，其實對 n 是指數級的，因為 N = 2^n。把這點弄對，正是嚴謹課程總是說「時間是輸入大小的函數」的原因。
這也正是下一個概念「合理的編碼」之所以重要的理由：你怎麼寫下輸入，決定了 n 是多少，而一個耍詐的編碼可以讓慢演算法看起來快、或讓快演算法看起來慢。先固定一個合情合理的輸入寫法；接著「執行時間如何隨 n 成長？」這個問題才會有乾淨、與模型無關的答案。
對數字 1000 而言，作為二進位字串「1111101000」的輸入大小是 10 個位元，所以 n 大約是 10，而非 1000。一個對此輸入跑 1000 次的迴圈，相對於 n = 10 是做了 2^n 次（因為 2^10 = 1024），所以它對輸入大小是指數級的，儘管聽起來只是個小迴圈。
一個數值為 N 的單一數字，輸入大小約為 log N，所以「步數 = N」對輸入大小而言是指數級的。
輸入大小是寫下來的輸入的「長度」，不是它的數值：數字 N 的大小約為 log N，這正是「偽多項式」演算法（對 N 是多項式、對大小卻是指數級）並非真正高效的原因。