6 votes 6 votes $T(n) = 2T(\sqrt{n}) + n$ Algorithms algorithms time-complexity recurrence-relation + – Shubhanshu asked Jan 20, 2018 Shubhanshu 1.1k views answer comment Share Follow See all 14 Comments See all 14 14 Comments reply Show 11 previous comments Shubhanshu commented Jan 20, 2018 reply Follow Share @sumit goyal 1 f(k) which is 2^k (exponential function) is bigger than 2S(k/2). Hence, it will be the TC. or TC = O(2^k) or O(n) as 2^k = n. 0 votes 0 votes sumit goyal 1 commented Jan 20, 2018 reply Follow Share T(n) = $8T(\frac{n}{2})+ n^2$ answer = $\Theta (n^3)$ if i apply that logic here that n$^2$ >> T$(\frac{n}{2})$ = O($(n^2)$ it failed here not a good approach @Shubhanshu according to me bro 1 votes 1 votes sushmita commented Oct 5, 2018 reply Follow Share did u get the explanation here ? 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes it should be o(n) abhishekmehta4u answered Mar 10, 2018 • selected Feb 1, 2019 by Shubhanshu abhishekmehta4u comment Share Follow See all 0 reply Please log in or register to add a comment.
