Основная теорема с логом

Question

Вот problem.

Я действительно путают о c равна 0.5 части. На самом деле в целом я смущен, как logn может стать n^(0.5). Не могу ли я просто оставить c равным 100, что будет означать 100 < d, в результате чего используется другой случай? Что мне здесь не хватает?

Answer 1

Вы конечно мог установить c = 100 так что n^c является (очень, ооочень) грубый асимптотический верхней границей log(n), но это даст вам ужасающее и абсолютно бесполезную оценку на вашем выполнении T(n).

Что вам скажут, это то, что каждая функция полинома n^c растет быстрее, чем логарифм, независимо от того, насколько мала c, до тех пор, пока она остается положительной. Вы могли бы взять c=0.0000000000001, он, казалось бы, стал бы смехотворно маленьким в начале, но в какой-то момент он стал бы больше log(n) и расходился бы до бесконечности намного быстрее, чем log(n). Поэтому, чтобы избавиться от термина n^2 log(n) и иметь возможность применить версию теоремы Мастера только по полиномиальному принципу, верхняя граница логарифмического термина определяется тем, что растет медленно (но все же быстрее, чем log(n)). В этом примере достаточно n^c с c=0.5, но вы также можете взять c=10^{-10000} «просто чтобы убедиться».

Затем вы применяете теорему Учителя и получаете разумную (и резкую) асимптотическую верхнюю границу для вашего T(n).