Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 20

Рассмотрим следующие три утверждения

1. (n + k)m = Θ(nm), where k and m are constants
2. 2n + 1 = O(2n)
3. 22n + 1 = O(2n) 

Какие из этих утверждений верны?

(А) 1 и 2
(Б) 1 и 3
(С) 2 и 3
(D) 1, 2 и 3

Ответ: (А)
Объяснение: (n + k) m и Θ (n m ) асимптотически совпадают с тэта-нотацией, которую всегда можно записать, взяв член начального порядка в полиномиальном выражении.

Рекомендуемые посты:

ВОРОТА | GATE-CS-2003 | Вопрос 20

0.00 (0%) 0 votes