0 votes 0 votes Algorithms recurrence-relation + – Sharmila salam asked May 22, 2017 • retagged Jun 20, 2022 by makhdoom ghaya Sharmila salam 505 views answer comment Share Follow See 1 comment See all 1 1 comment reply Surajit commented May 22, 2017 reply Follow Share Substitute n = 2^m ...then subsitute T(2^m) = S(m)..then apply masters theorem. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes T(n) = T(sqrt n) +1 let n = 2m .........................(1) T(2m) = T(2m/2) + 1 assume T(2m) = S(m) so S(m) = S(m/2) + 1 apply master theorem S(m) = theeta (log m) from (1) so T(n) = theeta (log log n) pawan kumarln answered May 22, 2017 pawan kumarln comment Share Follow See all 0 reply Please log in or register to add a comment.