Time Complexity of operation - Python

Question

I was wonder what the time complexity of certain operation in python are:

x = k * l ( multiplication )

x = k/l ( division )

math.sqrt(y)

math.pow(y,f)

and what is the complexity for using a while - loop.

knh190 · Accepted Answer · 2019-04-04 08:49:06Z

4

I truly believe it's the same in Python as in every other common languages?

x = k * l # multiplication  -> O(n²)

x = k/l # division -> O(n²)

math.sqrt(y) # -> O(M(n))

math.pow(y,f) # -> O(M(n))k), n digits number and k bit exponent 

while loop # -> O(n) ,same as For loop.

Edit : For multiplication, Python uses the standard multiplication algorithm O(n²) but for very big numbers, it goes with Karatsuba algorithm, so O(n^1.585) according to wikipedia.

edited Apr 4, 2019 at 8:49

knh190

2,8821 gold badge21 silver badges32 bronze badges

answered May 17, 2017 at 9:05

rilent

7321 gold badge7 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Time Complexity of operation - Python

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related