0 votes 0 votes T(n) = T(sqrt(n)) + n Taking 2m = n we can convert this as S(m/2) + 2m after this how to solve by masters? Algorithms recurrence-relation + – A_i_$_h asked Nov 16, 2017 • edited Jun 25, 2022 by makhdoom ghaya A_i_$_h 513 views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments Rupendra Choudhary commented Nov 18, 2017 reply Follow Share forget what's standard form of master theorem. if f(x) is some exponential function that directly say TC would be of exponential growth. 0 votes 0 votes Ashwani Kumar 2 commented Nov 19, 2017 reply Follow Share @Aish We cant compare both of the recurrence relation as General form is $T(n)=aT(\frac{a}{b}) + n^{k} log^{p}n$ but what we got is $T(m)=T(\frac{m}{2})+2^{m}$, as here constant raise to the variable but we have in general form we have variable raise to the power constant...isn't it? We can solve it either by substitution or by we can think $T(m)=T(\frac{m}{2})+2^{m}$ as a problem is divided into one subproblem of size half of the original problem and the time to solve or divide each subproblem is exponential itself so overall time complexity will definitely be exponential, hence we can write $T(m)=\Theta (2^{m})$ or $T(n)=\Theta (n)$ 1 votes 1 votes A_i_$_h commented Nov 20, 2017 reply Follow Share @ashwani @rupendra tanku :) 0 votes 0 votes Please log in or register to add a comment.
–1 votes –1 votes T (n)=T (n^1/2) + n Divide by n T (n) / n = T (n1/2)/n + 1 Consider n=2m S (m) = T (n)/n S (m)= S (m/2) + 1 S (m) = logm Now, logm= T (n)/n T (n) = n×logm Since, n=2m or m=logn T (n) = n log(log n) Abbas2131 answered Nov 16, 2017 Abbas2131 comment Share Follow See all 0 reply Please log in or register to add a comment.