Доказательство того, что различные среды выполнения имеют различные сложности Big-O

Question

Как мне доказать следующее:

1. 10 n log n ∈ O (2n ² )

2. n log n + 40 · 2 ⁿ - 6n ∈ O (2 ⁿ )

В первом я использую этоматематика:

10 n log n ≤ c · 2n ²

10 n ² ≤ c · 2n ² делим на 2

5 n ² ≤ c · n ²

Я предполагаю, что c = 5 и n ₀ = 1, но я не уверен, что это правда.

Во втором я попытался умножить левую часть на 2 ⁿ , но этоне работалУ кого-нибудь есть предложения?

Answer 1

Для части (1) вы хотите доказать

10 n log n = O (2n ² )

Это может помочь заметить, что для любого n & ge; 1, что

log n

Следовательно, у вас есть это

10 n log n & le; 10 n ² = 5 (2n ² )

Таким образом, вы можете сделать вывод, что 10n log n = O (2n ² ), поскольку вы можете выбрать n ₀ = 1 и c = 5 и использовать формальное определение больших О.

Для части (i) вы хотите доказать

n log n + 40 & middot; 2 ⁿ - 6n = O (2 ⁿ )

Один полезный факт, который вы можете здесь использовать, состоит в том, что n ² & le; 2 ⁿ для любого n & ge; 4. Поэтому мы получаем это всякий раз, когда n & ge; 4

n log n + 40 & middot; 2 ⁿ - 6n & le; n log n + 40 & middot; 2 ⁿ & le; 40 & middot; 2 ⁿ + n ² & le; 40 & middot; 2 ⁿ + 2 ⁿ = 41 & middot; 2 ^п

Поэтому, если вы выберете n ₀ = 4 и c = 41, вы можете использовать формальное определение big-O, чтобы доказать, что n log n + 40 & middot; 2 ⁿ - 6n = O (2 ⁿ ).

Надеюсь, это поможет!