ВОРОТА | 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 ) асимптотически совпадают с тэта-нотацией, которую всегда можно записать, взяв член начального порядка в полиномиальном выражении.

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

• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 52
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 65
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 64
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 53
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 54
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 55
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 56
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 57
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 58
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 59
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 60
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 61
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 62
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 63
• ВОРОТА | Sudo GATE 2020 Mock II (10 января 2019 года) | Вопрос 65