Как определить, находится ли функция f в тета (g)

Question

Полное раскрытие: это домашнее задание. Честно говоря, я немного волнуюсь, что меня так долго избегали, когда это казалось таким простым.

Хорошо, вопрос в том, что f (n) = n ^ 2 * log (n), g (n) = n ^ 2.1. Находится ли f в тета (г)?

Мне просто нужно придумать константы c ₁ , c ₂ , так что после определенного n ₀ , f (n) <= c <sub>1 g (n) <= c <sub>2 f (n). Но я даже не уверен, что f находится в тета (g) вообще. Я в замешательстве.

Answer 1

Из того, что я помню, чтобы доказать, что f (n) находится в тета (g (n)), вы можете использовать два разных подхода:

1. Докажите, что f в O (g), и докажите, что g в O (f).

2. Докажите, что f в O (g), и докажите, что f в BigOmega (g).

Answer 2

Сначала обратите внимание на формулировку.«Находится ли в тета (г)».Это означает, что они хотят, чтобы вы сначала сделали обоснованное предположение о том, правда ли это.

Встречный вопрос: является ли theta (n) тем же, что и theta (n * log (n))?Мы знаем ответ на этот вопрос ... нет, это не так (в противном случае сортировка на основе сравнения была бы линейной, например).Что это говорит о вашем вопросе?

Чтобы доказать это утверждение, следуйте другому ответу MahlerFive.Для полноты, чтобы попытаться опровергнуть утверждение, предположим, что враг придумал константы c1 и c2.Теперь наша цель - показать, что, несмотря на то, какие константы возникли у противника (то есть для всех c1 и c2), нет n0, удовлетворяющих ограничению.Другими словами, покажите, что вы не можете выбрать c1 и c2.Уловка в вашем случае, вероятно, сосредоточена вокруг log (n) -фактора в функции f.log (n) монотонно возрастает, что говорит о том, что мы можем сделать этот фактор сколь угодно большим, подключив большее значение n.

Я надеюсь, что это немного продвинет вас вперед, пока вы не удовлетворены решением проблемы самостоятельно.Если я полностью неправ, я уверен, что другие читатели меня поправят.