Complexity of square root

[gian]

Hello,

I have an assignment problem regarding complexity.

I need to find the square root of a number and I need to do that in two ways. Efficiently and not so efficiently..

Problem is I am having some problem, dealing with the complexity, I had studied a bit on it on the past but I seem to forget easily. Any tips on how to find the complexity of a recursive algorithm?

Can anyone tell me what's the complexity on a recursive Newton algorithm to find the root square?

I wrote 2 algorithms, my first one was supposed to be slow and the second faster, but erm well the first one is lighting fast :p so if you can help me computate the time complexity...

sqrt n xs =
 if (head xs * head xs <= n) then sqrt n (tail xs)
 else head xs - 1 

notsofastisqrt n = myisqrt n n 
       where isqrt y n = if abs(y*y - n) <= 1
                          then  truncate y
                          else isqrt ((y+(n/y))/2) n

Thanks a lot..