Обучение для моего финала: Асимптотическая нотация

Question

В настоящее время я изучаю свое окончательное решение в алгоритмах. Это не проблема домашних заданий и происходит из старого финального экзамена.

Show that f(n) = 4logn + log log n is big theta of logn. 

Очевидно, что log log n значительно меньше log n и, следовательно, несуществен. Но как я могу показать это формально? Я знаком с ограничениями и L'hopital, поэтому я был бы признателен, если вы сможете показать мне, как это сделать с помощью этого метода.

Answer 1

Помните определение большой тета. Функция f(x) в Theta(g(x)) если

Вы f(x) = 4*log(x) + log(log(x)) и g(x) = log(x). Теперь мы должны показать, что существуют значения для c_0, c_1 и x_0, которые удовлетворяют условию.

Если мы возьмем c_0 = 1 и x_0 достаточно велико, что log(log(x_0)) > 0 (точное количество зависит от основания вашего логарифм, но всегда есть такое число, и мы на самом деле не нужно знать это), то это довольно легко чтобы показать, что первое неравенство справедливо для всех x > x_0: log(x) <= 4*log(x) + log(log(x)) (подсказка:. log(log(x)) уже > 0 и функция логарифм является монотонно возрастающей

Теперь давайте выберем c_1 = 5 Второе неравенство теперь становится 4*log(x) + log(log(x)) <= 5*log(x), что упрощает для

.

log(log(x)) <= log(x) 

для всех x > x_0. Я оставлю это доказательство вам как упражнение. :-)

Answer 2

Легкий способ нахождения c1, c2 и нет.

Поиск верхняя граница:

f(n) = 4logn+loglogn 


    For all sufficience value of n>=2 

     4logn <= 4 logn 
     loglogn <= logn 

    Thus , 

    f(n) = 4logn+loglogn <= 4logn+logn 
          <= 5logn 
          = O(logn)  // where c1 can be 5 and n0 =2 

Поиск нижней границы:

f(n) = 4logn+loglogn 

    For all sufficience value of n>=2 

     f(n) = 4logn+loglogn >= logn 
    Thus,    f(n) = Ω(logn) // where c2 can be 1 and n0=2 


    so , 
         f(n) = Ɵ(logn)