Time comparisons between two algorithms that evaluate the gcd of the two numbers

In this article let us study the time comparison of the two algorithms to evaluate the gcd of two numbers.

Algorithm 1: It is basically Euclid’s Algorithm. For time complexity details please feel free to refer the below link

Time complexity of Euclid’s Algorithm

Algorithm 2: It is based on the basic definition of gcd. It takes O(n).

Here are the code implementation and output.

Code is written in CPP:-

Algorithm 1:- Faster

Algorithm 2:- Slower

IDE | GeeksforGeeks | A computer science portal for geeks

Please Don’t try to run the code at the geeks for geeks ide, it will not work. Run it on the local machine. After sufficient time you can generate interrupt and stop the program.

Here is the snapshot of the output Generated on my computer.

Output

Here we can see how clever the algorithm 1 is. It takes only 0 Milli sec time to complete such a large problem but algorithm 2 takes a huge amount of time on the other hand.

On further increasing the value of n. It will be impossible by the computer to evaluate the gcd of the number using an algorithm 2, on the other hand, it will take even less than a second using algorithm 1.

This shows how important is to select the algorithm.

Hope it matters!!!

Happy Coding.