Как получить Омега (н)

Question

У меня есть формула a(n) = n * a(n-1) +1; а (0) = 0

Как я могу получить Omega, Theta или O Notation из этого без основной теоремы, или у кого-нибудь был хороший сайт, чтобы понять объяснение

Answer 1

Основная теорема даже не применима, поэтому отсутствие возможности ее использования не является большим ограничением.

Подход, который работает здесь, состоит в том, чтобы угадать верхнюю и нижнюю границы, а затем доказать эти догадки по индукции, если догадки хорошие.

a(0) = 0
a(1) = 1
a(2) = 3
a(3) = 10
a(4) = 41

Разумным предположением для нижней границы является то, что a(n) >= n! для n>1. Это верно для n = 1. Предположим, что это верно для n=k-1.

a(k) = ka(k-1)+1 
     >= k (k-1)! + 1 
     >= k!. 

Итак, если это верно для n=k-1, то это верно для n=k, поэтому a(n) >= n! для всех натуральных чисел n и a (n) = Омега (n!).

Разумным предположением для верхней границы является a(n) <= 2(n!). Это верно для первых нескольких значений, но оказывается немного неловко доказывать использование индукции. Иногда с помощью индуктивных доказательств лучше доказать что-то более сильное. В этом случае лучше доказать, что a(n) < 2(n!) Или a(n)<=2(n!)-1. Это верно для n = 1. Предположим, что это верно для n = k-1 для некоторого k-1>=1. затем

a(k) = k(a(k-1))+1 
    <= k(2(k-1)!-1)+1 
     = 2(k!) +1-k 
    <= 2(k-1)!-1. 

Таким образом, для любого n>=1 a(n) < 2(n!). Так как у нас есть нижняя граница и верхняя граница вида c*(n!), A (n) = Theta(n!).

Answer 2

Вы уже заметили, что ваша формула очень близка к факториалу n!, Теперь вы можете выразить этот вывод более формально: например, вы можете доказать, что

n! < a(n) < 2*n! (for big enough n)

Если это правда, то все O, Θ а также Ω являются n!,

Я полагаю, что вы можете доказать вышеупомянутое неравенство или какой-то другой вариант, используя индукцию (хотя и не пробовал).

Answer 3

Подсказка:

Разделив a(n) на n!, первые члены

a(1)/1! = 1/1! = 1
a(2)/2! = (2.1+1)/2! = 1 + 1/2!
a(3)/3! = (3.(2.1+1)+1)/3! = 1 + 1/2! + 1/3!
a(4)/4! = (4.(3.(2.1+1)+1)+1)/4!= 1 + 1/2! + 1/3! + 1/4!
...

Это устанавливает жесткий брекетинг

n! <= a(n) < (e-1).n!

а также a(n) в Θ(n!),