You are not logged in. Please login at to post your questions!


Built-in Power Function Complexity

Hi! Could anyone please tell me what is the complexity of built-in pow(a,b) function in <cmath> header file? Is it naive O(n) or O(log(n))? Thanks.

asked 29 Dec '14, 22:56

sidharthanegi's gravatar image

accept rate: 0%

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 .


answered 29 Dec '14, 23:02

mhungry's gravatar image

accept rate: 18%

@mhungry Thank You! That was helpful.

(30 Dec '14, 13:37) sidharthanegi3★

In python u can use function with mod tooo...such a great feature pow(a,b,mod) .

(10 Feb, 00:39) nikhil1424★

@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




answered 12 Jan '15, 02:16

saiavinashiitr's gravatar image

accept rate: 0%

edited 19 Jan '15, 03:47

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

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.. :)


answered 29 Dec '14, 23:18

damn_me's gravatar image

accept rate: 24%

edited 29 Dec '14, 23:51

@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!

(30 Dec '14, 13:40) sidharthanegi3★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 29 Dec '14, 22:56

question was seen: 17,636 times

last updated: 10 Feb, 00:39