# Built-in Power Function Complexity **URL:** \ **Category:** general\ **Tags:** programming\ **Created:** [December 29, 2014, 10:56pm UTC](https://discuss.codechef.com/t/built-in-power-function-complexity/8901 "2014-12-29T22:56:26Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![sidharthanegi](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sidharthanegi](https://discuss.codechef.com/u/sidharthanegi)\ **Post date:** [December 29, 2014, 10:56pm UTC](https://discuss.codechef.com/t/built-in-power-function-complexity/8901/1 "2014-12-29T22:56:26Z")
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. ---
**Author:** ![mhungry](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@mhungry](https://discuss.codechef.com/u/mhungry)\ **Post date:** [December 29, 2014, 11:02pm UTC](https://discuss.codechef.com/t/built-in-power-function-complexity/8901/2 "2014-12-29T23:02:33Z")
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 . ---
**Author:** ![damn\_me](https://discuss.codechef.com/user_avatar/discuss.codechef.com/damn_me/32/208155_2.png) [@damn\_me](https://discuss.codechef.com/u/damn_me)\ **Post date:** [December 29, 2014, 11:18pm UTC](https://discuss.codechef.com/t/built-in-power-function-complexity/8901/3 "2014-12-29T23:18:28Z")
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](http://stackoverflow.com/questions/4638473/how-to-powreal-real-in-x86). 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](http://stackoverflow.com/questions/2284860/how-does-c-compute-sin-and-other-math-functions), awesome answers… 🙂 ---
**Author:** ![saiavinashiitr](https://discuss.codechef.com/user_avatar/discuss.codechef.com/saiavinashiitr/32/6955_2.png) [@saiavinashiitr](https://discuss.codechef.com/u/saiavinashiitr)\ **Post date:** [January 12, 2015, 2:16am UTC](https://discuss.codechef.com/t/built-in-power-function-complexity/8901/4 "2015-01-12T02:16:50Z")
@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: > **[SPOJ.com - Problem LASTDIG](https://www.spoj.com/problems/LASTDIG/)** > > ... Explaination: > **[Exponentiation by squaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring)** > > In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like e... ---
**Author:** ![sidharthanegi](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sidharthanegi](https://discuss.codechef.com/u/sidharthanegi)\ **Post date:** [December 30, 2014, 1:37pm UTC](https://discuss.codechef.com/t/built-in-power-function-complexity/8901/5 "2014-12-30T13:37:50Z")
@mhungry Thank You! That was helpful. ---
**Author:** ![sidharthanegi](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sidharthanegi](https://discuss.codechef.com/u/sidharthanegi)\ **Post date:** [December 30, 2014, 1:40pm UTC](https://discuss.codechef.com/t/built-in-power-function-complexity/8901/6 "2014-12-30T13:40:42Z")
@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! ---
**Author:** ![nikhil142](https://discuss.codechef.com/user_avatar/discuss.codechef.com/nikhil142/32/28951_2.png) [@nikhil142](https://discuss.codechef.com/u/nikhil142)\ **Post date:** [February 10, 2019, 12:39am UTC](https://discuss.codechef.com/t/built-in-power-function-complexity/8901/7 "2019-02-10T00:39:20Z")
In python u can use function with mod tooo…such a great feature pow(a,b,mod) .