Page 4 - Lesson Note-Algorithmic Efficiency

Comparison of Algorithm
There can be more than one approach Prime numbers are of great importance in computer
science as they find application in databases, security, file compression or decompression,
modulation or demodulation, etc. There can be different ways to write algorithms to check
whether a given number is prime or not as shown below:

Check the divisibility if N=19391
Methods Time Complexity
from No of steps required
Method 1 1 to N O(n) 19391
Method 2 2 to (N/2) O(n/2) 9694
Method 3 2 to √ O(√ ) 138( √ = 139.3)
2 to √ ,
√
Method 4 but discard all even O( ) 69(approx.)
2
divisors except 2