Наверное часто вы слышали фразы типа "сложность алгоритма сортировки - N*LogN" или "алгоритм Флойда имеет сложность N^3". Эти выражения показывают, насколько быстро увеличивается время работы алгоритма с увеличением размерности.
Примеры:

a[1]:=10 Сложность O(1)

for i:=1 to n do a[i]=i Сложность O(n)

for i:=1 to n do
  for j:=1 to n do
    a[i]=a[i]+a[j] Сложность O(n^2)

for i:=1 to n do
  for j:=1 to 100000 do
    a[i]=a[i]+1 Сложность всё-равно O(n), т.к время работы увеличивается линейно