analysis of algorithm

Question

Answer 1

Ans is A.

In these type questions where √  is given take n= 2^m

so, √ n =2^(m/2)

now substitute the respective powers of n for m

T(m) =T(m/2) + logm

Solving by Master's Theorem u get-->

log m * log m

now replacing m by log n (since n= 2^m) we get

θ (log log n) ^2  as ans..

Comments

With Reference to your solution I have a doubt sir,

In the Step of your solution:

now substitute the respective powers of n for m

T(m) =T(m/2) + logm

----------------------------------

according to this : after substitution the equation will became like:

T(m) =T(m/2) + loglogm    ???is'nt

because
T(2^m)=T(2^m/2)+loglog(2^m) ...is the expression formed after subsituting n=2^m

is'nt Please Clearify sir....

Thanks

---

First of all I am no SIR..! :)

loglog(2^m) = log(m log 2)

                    =log m (since log2 is 1 as we have base as 2  in binary computations)

---

T(2^m)=T(2^m/2)+loglog(2^m)

after computing
T(2^m)=T(2^m/2)+logm
is the expression....my doubt is that How we can replace the above expression with
T(m)=T(m/2)+logm  .... if we take powers of 2 under consideration  then we are doing no justice to logm

---

why do u think that we are doing no justice to logm?