ВОРОТА | GATE-CS-2006 | Вопрос 51

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

Что из следующего верно?

(A) T (n) =

(Loglogn)
(B) T (n) =

(LOGN)
(C) T (n) =

(SQRT (п))
(D) T (n) =

(П)
(А) А
(Б) Б
(С) С
(D) D

Ответ: (Б)
Объяснение:

Необходимый фон — решение рекуррентности с использованием метода замещения.

Ответ — Б
Развертывание рекурсии,

T (n) = 2T (n ^ (1/2)) + 1
= 2 ^ 2T (n ^ (1/4)) + 2
= 2 ^ 3T (n ^ (1/8)) + 3
,
, k шагов
,
= 2 ^ кТ (n ^ (1 / 2k)) + k …………. (1)

Используя Базовый случай,

n ^ (1 / 2k) = 2
Принимая бревно с обеих сторон
log2n = 2k
k = log2log2n

С 1),

T (n) = log2n + log2log2n
= Тета (log2n)

Здесь log2n: log (база 2) n

Связанный :
http://geeksquiz.com/algorithms-analysis-of-algorithms-question-17-2/

Это решение предоставлено Пранджул Ахаджа .

Тест на этот вопрос

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

• ВОРОТА | 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