roycf123's blog

Time Complexity of std::sqrt() , O(sqrt(n)) or O(logn)?
By roycf123, history, 17 months ago, In English

Recently, I have encountered many situations in which I was asked the complexity of std::sqrt() in C++. Since my early cp days, I have known the time complexity of std::sqrt() to be O(sqrt(n)), the reason being this and a few other youtube channels. I was using C++17 at that point.

A friend of mine suggested it to be O(logn) in C++20 after he tested it by printing cout<<sqrtl(N), where N was set as 1e18. The code compiled in 10 ms, giving the correct ans.

Later on, I ran the same code in C++14 in ideone and the code still compiled in 10 ms. This made me really confused...

I would really appreciate if someone helps me with this. I looked it up in cpp-reference but couldn't find it.

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
17 months ago, # |
← Rev. 2   Vote: I like it +90 Vote: I do not like it

Ah, you made the rookie mistake of believing that everything on GFG is correct. There's a ton of articles on problems on GFG that contain mistakes or the solutions are simply just wrong.

I don't know how the std::sqrt is implemented, but as you saw, it runs very quickly. Implementing a square root function can easily be done with binary search — it wouldn't make any sense for the c++ library implementation to be slower.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah I always implement with binary search. Thanks for clarifying.

    → Reply
»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

There are several methods for computing square roots, using convergence of series, iterative methods, etc. This is from Wiki. Using a fixed number of iterations, you can get a better performance than log N. Someone told me once that C++ uses a table with precomputed values that make it faster.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Okay but how big would that table be? I mean sqrtl supports values upto 1e18, so I'm not able to understand what we would precompute to construct the answer in O(1).

    → Reply
»
17 months ago, # |
  Vote: I like it +31 Vote: I do not like it

In these benchmarks, it looks like std::sqrt is much faster than pretty much everything. In fact, if you look at the assembly, then in almost all cases (after doing some floating point checks), std::sqrt calls the hardware instruction sqrtsd, and I would expect hardware instructions to be much faster than software implementations.

→ Reply
»
17 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Ahahahahaha, then function pow(2, n) runs in $$$O(2^n)$$$ :D

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    correct me if im wrong, but its intended to be used with floats/doubles, no? there's no way for it to run in logn that way

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Apart from some special cases, it is usually implemented as $$$\text{pow}(x, y) = \exp(y \log x)$$$.

      → Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    C'mon bro, not funny :((..

    → Reply
»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Newton's method has a quadratic convergence rate which means that the number of accurate digits doubles with every iteration. This implies that for N-bit integers this method requires around log(N) iterations. Obviously std::sqrt might be even faster.

→ Reply