The Gateway to Computer Science Excellence

+1 vote

The solution of recurrence relation:

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

- $O(lg(n))$
- $O(n \: lg \: (n))$
- $O(lg \: (n) \: lg (n))$
- $O(lg \: (n) \: lg(lg \: (n)))$

+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) ) $

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) ) $

52,215 questions

59,981 answers

201,180 comments

94,638 users