title: What is the time complexity of the following function?
body: <pre><code>    int func(int n){
         if(n==1)
           return 0;
         else
           return sqrt(n);
      }
  </code></pre>
  
  <p>Where sqrt(n) is a C math.h library function.</p>
  
  <ol>
  <li>O(1)</li>
  <li>O(lg n)</li>
  <li>O(lg lg n)</li>
  <li>O(n)</li>
  </ol>
  
  <p>I think that the running time entirely depends on the sqrt(n). However, I don't know how this function is actually implemented. </p>
  
  <p>P.S. The general approach towards finding the square root of a number that I know of is using Newton's method. If I am not wrong, the time complexity using Newton's method turns out to be O(lg n). So should the answer be O(lg n)?</p>
  
  <p>P.P.S. Got this question in a recent test that I appeared for. </p>