We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
actually for both of the steps 1 & 2 the complexity will be O(n log(b)).
Here n is the length of the array and b is the smaller integer of a pair(a,b) for which we calculate the GCD/LCM.
For simplicity we call it O(n log(n)) instead of O(n log(b)).
Explanation:
To calculate the GCD or LCM for the whole array we need to run a loop up to the length of the array which is n and inside that loop we need to calculate GCD/LCM which will take log(n). like below.
Between Two Sets
You are viewing a single comment's thread. Return to all comments →
actually for both of the steps 1 & 2 the complexity will be O(n log(b)).
Here n is the length of the array and b is the smaller integer of a pair(a,b) for which we calculate the GCD/LCM.
For simplicity we call it O(n log(n)) instead of O(n log(b)).
Explanation: To calculate the GCD or LCM for the whole array we need to run a loop up to the length of the array which is n and inside that loop we need to calculate GCD/LCM which will take log(n). like below.
so the complexity is O(n*log(n)). Same goes for LCM also.