Hi! Could anyone please tell me what is the complexity of built-in pow(a,b) function in header file? Is it naive O(n) or O(log(n))? Thanks.
Hello Sidharthanegi
Complexity of inbuilt pow function.
for c or c++ O(log(N)) but as we know c++ does not support any inbuilt datatype which can handle such large values even 2^100 … It is usually avoided for large values .
for python O(log(N)) even there are other option available in that language .
I exactly didn’t get the intention behind your doubt I once had it though :P). But the main point is, complexity is what we call the estimation of the growth of the function with respect to the given input variable n. pow function always take same number of inputs, thus, constant input size, so there’s no point thinking about its complexity. But if we think in terms of bits, i.e. how every operation in measure of bits is happening internally, how the processor is computing it, then it depends on your underlying architecture(specifically processor). For a x86 processor, it is constant because it is calculated this manner:
//Assembly language code
2^(y*log2(x))
Instructions FLY2X and F2XM1 are used for this computation, for this see here. Because I have been working on assembly language and hardware side last weeks, I believe in this: For other functions of the math library and even this, they are implemented in microcodes inside microprocessors. A C compiler will generate codes that will call these assembly instructions. Nowadays, these instructions are sometimes quite inaccurate and are therefore rarely used anymore. Most other processors do not have instructions for sine and cosine because calculating them in software gives more flexibility, and may even be faster. Many implementations may be provided by the library we are using, no one software algorithm is efficient, this depends on our input size and the computations required. So, the first job of the library is to look which implementation of the given and required function will be appropriate.
Read more here, awesome answers… 
@damn_me What I meant by O(n) was infact O(b), the second argument of pow() funtion. My bad, I didn’t express myself clearly. Thanks though!
@sidharthanegi : i just want to share something useful related to your question.
if a and b are very large numbers the overflow might occur. In that case u can use Logarithmic Exponentiation which whose complexity is O(logn).
Below is the link for a problem in spoj where the exponent is a very large number … in that case you must use Logarithmic Exponentiation method to get the desired result and get accepted.
Also see the explaination by wikipedia below
Problem:
Explaination:
2 Likes
In python u can use function with mod tooo…such a great feature pow(a,b,mod) .