Share:
Notifications
Clear all

Number system

2 Posts
2 Users
0 Likes
790 Views
Ishita Jain
(@ishitajain)
Posts: 58
Trusted Member
Topic starter
 

Q. 4

1630834676-IMG_20210905_145454.jpg
 
Posted : 05/09/2021 3:07 pm
Rahul Singh
(@rahul)
Posts: 825
Prominent Member Admin
 
Let p and q be any two elements of set A.
For the computation of the GCF of elements of set A, we can replace both p and q by just the GCF(p,q) and the result is unchanged.
So, for every application of the function h, we are reducing the number of elements of the set A by 1. (In this case two numbers p and q are replaced by one number GCF(p,q)).
Expanding this concept further, the minimum number of times the function h should be called is n-1.
 
I hope this helps!
 
 
Posted : 07/10/2021 9:38 pm
Share: