The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
65 views

UGCNET-DEC2018-II-21.8

  1. UGCNET-DEC2018-II-105
  2. UGCNET-DEC2018-II-105
  3. UGCNET-DEC2018-II-105
  4. UGCNET-DEC2018-II-105

The solution of recurrence relation:

$T(n) = 2T (sqrt(n)) + lg(n)$ is

  1. $O(lg(n))$
  2. $O(n \: lg \: (n))$
  3. $O(lg \: (n) \: lg (n))$
  4. $O(lg \: (n) \: lg(lg \: (n)))$
asked in Others by Veteran (395k points)
edited by | 65 views

2 Answers

+2 votes
Best answer
By recursively applying the recurrence relation, we got

T(n) = $2^k . T(n^{\frac{1}{2^k}}) + k . lg n$

By taking Base condition, T(2) = 1 ( i assumed it, in the question they didn't specify it )

$n^{\frac{1}{2^k}} = 2 ===> 2^k = log_2n \;\;and\;\; k = log_2(log_2n)$

∴ T(n) = $log_2n . T(2) + log_2(log_2n) . log_2n$

∴ T(n) = $log_2n + log_2(log_2n) . log_2n = lg \;n + lg\;n . (lg\;lg\;n) = O(lg\;n . (lg\;lg\;n) ) $
answered by Veteran (60.2k points)
selected by
+1 vote

Option d is right.

answered by Boss (33.4k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,049 questions
53,194 answers
184,527 comments
70,400 users