What is the time complexity of math.Pow function?

[Jingguo Yao]

What is the time complexity of Math.Pow(x, y) function (https://golang.org/pkg/math/#Pow) in terms of x and y when the values of x and y are not for the special cases? I have skimmed the source code (https://golang.org/src/math/pow.go?s=1186:1216#L28). And it seems that the time complexity is O(log2(y)). So the time complexity for math.Pow(0.87, 16384) should be O(log2(16384)) = (log2(2^14)) = O(14).

Is my understanding correct?

[Keith Randall]

Yes, you are correct.

[Paul Hankin]

On Friday, 15 January 2016 01:36:39 UTC+9, Jingguo Yao wrote:

What is the time complexity of Math.Pow(x, y) function (https://golang.org/pkg/math/#Pow) in terms of x and y when the values of x and y are not for the special cases? I have skimmed the source code (https://golang.org/src/math/pow.go?s=1186:1216#L28). And it seems that the time complexity is O(log2(y)). So the time complexity for math.Pow(0.87, 16384) should be O(log2(16384)) = (log2(2^14)) = O(14).

Is my understanding correct?

Not exactly. For y < 2^63, there's a loop of size ceil(log_2(y)), but for larger y, the result is calculated using Exp(y * Log(x)).

Saying what the big-O time complexity is (or even what that means) is not so simple since the code is quite specific to the (bounded) float64 representation.

-- 

Paul

[Jingguo Yao]

Keith:

Thanks for your answer.

[navnee...@globallogic.com]

Yes 

because we use divide and conquer method to solve recursively the problem and get the solution in O(log(n)) times where n is the power

[3613_PRANAB NANDI]

can you please explain the logic or give a reference to the logic....

Go Green: Kindly don't print this unless so required.

Established U/S 3 of UGC Act and Accredited by NBA of AICTE and NAAC of UGC

Visit us @ http://www.kiit.ac.in

Follow us @ |Twitter|Facebook|Instagram|

The information contained in this electronic message and any attachments to this message are intended for the exclusive use of the addressee(s) and may contain proprietary, confidential or privileged information. If you are not the intended recipient, you should not disseminate, distribute or copy this e-mail. Please notify the sender immediately and delete all copies of this message and any attachments.  VIRUS WARNING: Computer viruses can be transmitted via email. The recipient should check this email and any attachments for the presence of viruses. The institute accepts no liability for any damage caused by any virus transmitted by this email.