complexity

Question

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?

Comments

forget what's standard form of master theorem.

if f(x) is some exponential function that directly say TC would be of exponential growth.

---

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

---

@ashwani @rupendra tanku :)

Answer 1

T (n)=T (n^1/2) + n

Divide by n

T (n) / n = T (n^1/2)/n + 1

Consider n=2^m

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=2^m or m=logn

T (n) = n log(log n)