The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
160 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 (406k points)
edited by | 160 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.9k points)
selected by
+2 votes

Option d is right.

answered by Boss (33.9k 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
49,539 questions
54,106 answers
187,297 comments
71,017 users