0 votes 0 votes The recurrence equation $T(n) = T(\sqrt{n}) + O(1)$ has the following asymptotic solution: $T(n) = O(\sqrt{n})$ $T(n) = O(\log n)$ $T(n) = O(n^{1/\log n})$ $T(n) = O(\log \log n)$ Algorithms uppcl2018 algorithms asymptotic-notation recurrence-relation + – admin asked Jan 5, 2019 retagged Apr 19, 2022 by Lakshman Bhaiya admin 281 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes $The\ given\ equation\ can\ be\ written\ as\ T(n)=T(\sqrt{n})+c \\and\ let\ n=2^{_{k}} \\T(2^{k})=T(2^{k/2})+c \\S=T(2^k) \\S(k)=S(k/2)+c \\after\ solving\ we\ get \\O(log_{2}k) \\subsitute\ k=log_{2}n \\Complexity\ will\ be\ O(log_2log_2n)$ Anurag Parothia 1 answered Jan 29, 2019 Anurag Parothia 1 comment Share Follow See all 0 reply Please log in or register to add a comment.