Let RELPRIME = { | x and y are positive integers that are relatively prime}. Giv

Question

Let RELPRIME = { | x and y are positive integers that are relatively prime}.  Given the following algorithm to test if two positive integers are relatively prime, let n be the maximum number of decimal digits in x and y.  Analyze the running time of this algorithm, using O notation.  Explain the details and give your reasoning for each step.

On input <x, y> where x and y are positive integers.

1.Repeat until y = 0:

2.Assign x x mod y.

3.Swap x and y.

4.Output x. If the result is 1, accept; otherwise reject.

Explanation / Answer

consider an example to explain the agorithm give above

here we take

X=98

and y=42

step 1:

since y is not equal to 0

so assign

x<-x mod y

X<- 98 mod 42 =14

now we have to swap the two values i.e

x becomes 42 now and y becomes 14

since again y is not equal to 0

then

onceagain the algo assigns

x<- x mod y = 42 mod 14 =0

now x became 0

here from the algo we have to swap X and Y

so X becomes 14 and Y becomes 0

since here the value of Y became 0 so it exits from the algorithm

since now the value of X is not equal to 1, so the two numbers are not relatively prime and hence is rejected.

Complexity is O (n)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.