Повторение основной теоремы: что такое полиномиальное различие?

Question

Таким образом, основная теорема неверна, если разность между f (n) и n^log_b(a) не является полиномиальной разницей. Означает ли полиномиальная разница соотношение между f (n) / n^log_b(a)? Я знаю, что если отношение является log (n), то теорема неверна. Но если отношение между ними равно n^C, где c - некоторая константа, значит ли это, что она верна? Есть ли предел тому, насколько маленький C может быть? Это может быть п ^0,3?

Answer 1

 T (n) = 2T (n/2)+ n/ log n

Здесь мы не можем применить основную теорему (неполиномиальная разница между f(n) и n log_b(a))

(n/logn)/ n^log_2(2) = logn which is not == n^c для любого c действительным числом

Полиномиальное различие означает:

f(n) / n log_b(a) == n^c

где с может быть любым положительным действительным числом.