CODEWITHSUNDEEP
algorithmmathtime-complexitymultiplication
Aymane Hrouch
Aymane Hrouch

Reputation: 103

Egyptian multiplication algorithm complexity?

I do understand the algorithm but can't find a way to define its complexity, the only thing i know is it have something to with the second parameter, because if it was smaller the steps will be fewer. Do you have any idea how can i do this? and is there any general way to define time complexity for any given algorithm?

egyptian multiplication algorithm:

def egMul(x, y):
res = 0
while(y>0):
    if(y%2==0):
        x = x * 2
        y = y / 2
    else:
        y = y - 1
        res = res + x
return res

Upvotes: 0

Views: 431

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58339

This code performs Theta(log(y)) arithmetic operations. By considering the binary representation of y, you can see it performs the else branch for each 1 that appears in the binary representation, and it performs the first branch of the if (the one that divides y by 2) floor(log_2(y)) times.

Upvotes: 0

Related Questions