Computer Science · Ch 4 — Introduction to Problem Solving
Comparison of Algorithm
4.7
Comparison of Algorithm
A problem solvable by computer can usually be approached in more than one way — which means more than one algorithm can exist for it. That immediately raises the question: which algorithm should we use?
A case study: testing whether a number is prime
Prime numbers matter greatly in computer science — they find application in databases, security, file compression/decompression, and modulation/demodulation, among others. Consider the problem of checking whether a given number is prime. Four different algorithms can be written:
- Trial division up to the number itself. Starting with divisor 2, divide the given number (the dividend) and check whether any factor exists. Increase the divisor by one in each iteration and repeat as long as the divisor is less than the dividend. If a factor turns up, the number is not prime.
- Trial division up to half the number. Same as (1), but test divisors only up to half of the dividend — a divisor can never be more than half of the dividend.
- Trial division up to the square root. Same idea again, but test divisors only up to the square root of the number.
- Division by a stored list of primes. Given a prior list of the prime numbers up to 100, divide the given number by each number in that list. If it is divisible by none of them, the number is prime; otherwise it is not.
All four methods correctly decide primality. Which is better, or more efficient?
- Algorithm (1) performs a large number of calculations — more processing time — because it keeps checking every possible divisor right up to the number. For a large input, it takes the longest to produce output.
- Algorithm (2) is more efficient than (1): checking only up to half the number cuts the computation time.
- Algorithm (3) is more efficient still: stopping at the square root reduces the work much further.
- Algorithm (4) does the fewest divisions of all, since it divides only by primes smaller than the number. But there is a price: the list of primes must be stored first, so this method consumes additional memory even though it needs fewer calculations.
Time complexity and space complexity
The comparison above generalises. Algorithms are compared and analysed on the basis of: …