Блог

Докажите или опровергните следующие утверждения:

1. Существующая функция f(n) so f(n-k) не равна Big-theta (f(n)) . когда k>=1 и является положительной константой.

Существует ли какая-либо функция, для которой это утверждение верно? Я думал об f(n)=n! , но я не уверен, что это правильный ответ. Более того, если f(n)=n! верно, то как это утверждение может быть доказано?

2. Существуют функции so (f(n))^2=Big-O(f(n)) и f(n)=Big-omega (log(log(n))) .

Я думаю, что нет функции, которая делает утверждение истинным. Если это правильно — как это можно доказать?

1. Исправьте для f (n) = n!. Достаточно показать, что для любого фиксированного k >= 1, (n — k)! не является Omega (n!), как и для любой константы c > 0, она выполняется для всех n, достаточно больших, чтобы c * n! > (n — k)!.

2. Не существует f (n) такого, чтобы оба f (n) ^ 2 = O (f (n)) и f (n) = Omega (log log n). Последнее подразумевает, что для некоторой константы c > 0 и всех n достаточно больших значений f (n) > c log log n и, в частности, f (n) > 1 для всех n достаточно больших значений. Если мы теперь предположим, что f (n) ^ 2 = O (f (n)), то существует константа r > 0, так что для всех n достаточно больших f (n) ^ 2 < r * f (n), а именно f (n) < r . Но это подразумевает, что log log n < (r / c) для всех n достаточно больших, что неверно для всех n > e ^ (e ^ (r / c)) (где e является основой log).