Почему третий случай основной теоремы здесь не применим T(n)=2T(n/2)+nlgn

Question

Почему nlgn полиномиально больше n, когда:"Полиномиально больше" означает, что соотношение функций падает между двумя полиномами асимптотически

Здесь n^0,1

Вот график зависимости y=n^0.1,y=log n и y = n^0.4 https://www.desmos.com/calculator/vjq0j1ri3f

Answer 1

Здесь n^0.1

Откуда вы взяли эту идею?

Смотрите этот пост Math SE. Следовательно, log n меньше любого положительного степенного полинома; следовательно, здесь применим случай 2 основной теоремы, а не 3. Продолжайте, и вы получите T(n) = Θ(n (log n)^2),