+1 vote
87 views

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)))$
edited | 87 views

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) )$
selected by
+1 vote

Option d is right.

+1 vote