Как доказать асимптотические обозначения

Question

Я хочу доказать следующее утверждение

2^(⌊lg n⌋+⌈lg n⌉)∕n ∈ Θ(n)

Я знаю, что, чтобы доказать это, мы должны найти константы c1>0, c2>0 и n0>0 такие, что

c1.g(n) <= f(n) <= c2.g(n) for all n >= n0

Другими словами, мы должны доказать f(n) <= c.g(n) and f(n) >= c.g(n).

Проблема в том, как доказать левую сторону (2^(⌊lg n⌋+⌈lg n⌉)∕n)

Спасибо

Answer 1

Вот вывод для верхней границы:

2^(⌊lg n⌋+⌈lg n⌉)/n
= 2^(2⌊lg n⌋+1)/n 
<= 2^(2 lg n + 1)/n
= 2^(2 lg n) 2^(1) / n
= 2 n^2 / n
= 2 n
= O(n)

Итак, мы знаем, что ваша функция может быть ограничена сверху на 2 * n.Теперь мы делаем нижнюю границу:

2^(⌊lg n⌋+⌈lg n⌉)/n
= 2^(2⌈lg n⌉ - 1) / n
>= 2^(2 lg n - 1)/n
= 2^(2 lg n) 2^(-1) / n
= 1/2 n^2 / n
= 1/2 n
= O(n)

Теперь мы знаем, что ваша функция может быть ограничена снизу с помощью n / 2.

Проверено на gnuplot;эти ответы выглядят хорошо и плотно.Это чисто алгебраическое решение, использующее определение, если функции floor () и floor ().

Answer 2

Вы можете начать с расширения экспоненциальной.Он равен n1 * n2 / n, где n1 <= n <= n2, 2 * n1> n и n * 2> n2.Остальное должно быть легко.