Suitability of Algorithms (OCR A Level Computer Science)

Suitability of Algorithms

Why do we Need to Check the Suitability of Algorithms?

• Algorithms must be compared to check the suitability for a specific set of data

• Algorithms can be compared to determine how long they take to solve a particular problem and how much memory they require to solve problems

• Generally, algorithms that finish quicker and use less memory are preferred

• The measurement of time for an algorithm to complete is called “time complexity” whereas the measurement of memory is called “space complexity”

Time Complexity

• To measure time complexity, the execution time in terms of operations or steps performed is compared, not the numerical time taken in seconds and minutes

• It is important to understand that an algorithm's time complexity is independent of the hardware and CPU used to run it. This means a faster CPU with higher clock speed will still take the same number of steps or instructions to execute the algorithm compared to a slower CPU with lower clock speed

  • An analogy would be running a marathon. The marathon distance and course is the algorithm, whereas the runners are different CPUs with different speeds. The runners will complete the marathon with different times but the marathon is still the same distance

  • Alternatively, students completing several exam papers. Each exam has a different number of questions (like the number of instructions in an algorithm). Each student acts like a CPU. Some students will finish the exams faster than others. The number of questions are the same however for each student

• The following algorithm calculates the sum of the first n integers:

function sumNumbers1(n)
	sum = 0
	for i = 1 to n
		sum = sum + n
	next i
	return sum
endfunction

• Compare this to the algorithm below which also calculates the sum of the first n integers

function sumNumbers2(n)
	sum = n * (n+1)/2
	return sum
endfunction

• Both algorithms above complete the same task, however the latter algorithm, sumNumbers2, is far more efficient in terms of the number of instructions executed

• In sumNumbers1, the number of instructions executed are as follows:

  • +1 for (sum = 0)

  • +n for (for i = 1 to n)

• The total number of instructions is therefore n+1. If n, the quantity of integers, is 10, then the total number of instructions executed is 11. If n is 1,000, then the total number is 1001

• As n increases, the (sum = 0) line becomes more and more insignificant in contributing to the overall time complexity. As n increases, the algorithm becomes more inefficient

• As n increases the time complexity of the algorithm becomes dependent on n

  • For further context, compare this to numerical time. If each instruction took one second to execute and if n is 1,000, then the algorithm would take 1,001 seconds to complete, where as if n is 10, it would take 11 seconds to complete

• In sumNumbers2, the number of instructions executed are as follows:

  • +1 for (sum = n * (n+1)/2)

• The total number of instructions is therefore 1. If n, the quantity of integers, is 10, then the total number of instructions executed is 1. If n is 1,000, then the total number is still 1

• No matter how big n becomes, sumNumbers2 always takes the same amount of time. Its time complexity is constant

• It is important to recognise that both algorithms share the same goal but complete them in very different ways

Space Complexity

• Space complexity is defined as how much memory an algorithm requires to complete

• If additional space is required to duplicate the data for example, this will contribute to the overall space complexity