Začali sme tu spomínať "veľkosť vstupu". Čo to vlastne je? Formálne ju môžeme definovať ako počet znakov potrebných na jeho zapísanie. V našej situácii je teda totožná s veľkosťou vstupného súboru, uloženého na disku.
Často sa stretneme s tým, že súčasťou vstupu je jedno číslo, ktoré je
úmerné jeho veľkosti. Napr. v Príklade 2 bude veľkosť vstupného súboru
(ktorý obsahuje $N$ a čísla z poľa A ) rádovo $4N+4$. Presné číslo závisí od
architektúry systému, ale vždy bude veľkosť vstupu lineárna od $N$.
V podobných prípadoch môžeme pre jednoduchosť za veľkosť vstupu považovať toto číslo. Preto napríklad v príkladoch o poliach či reťazcoch považujeme za veľkosť vstupu ich dĺžku. Všimnime si, že v grafových úlohách môže veľkosť vstupu závisieť od dvoch čísel: počtu vrcholov ($N$) a počtu hrán ($M$).
V podobnom duchu budeme vo zvyšku tohto textu používať na označenie veľkosti vstupu písmeno $N$.
Pozor ale na jeden nepríjemný špeciálny prípad. Na zapísanie jediného (veľkého) čísla nám stačí priestor logaritmický od jeho veľkosti. Totiž pripísaním ďalšej cifry na koniec sa číslo zdesaťnásobí, ale jeho dĺžka zväčší len o $1$. Teda napríklad na zapísanie čísla $123456$ nám stačí rádovo $\log_{10}\left( 123456 \right)$ cifier. Preto napríklad triviálny algoritmus na testovanie prvočíselnosti nepovažujeme za polynomiálny algoritmus – jeho dĺžka behu totiž nie je polynomiálna od veľkosti vstupu. (Ak si tomuto odseku nerozumel, nevadí, neskôr sa k tomu ešte vrátime.)