Algorithms — common mistakes

In an exam, if a question asks you to choose a search algorithm, always check if the data is described as sorted. If it is, Binary Search is likely the intended answer due to its efficiency. If not, you must mention that the data would need to be sorted first, or choose Linear Search.

When completing a trace table in an exam, be methodical. Use a pencil and ruler to keep your columns aligned. Write down the value of a variable in a new row every time it changes. If a variable doesn't change during a step, you may be required to copy its previous value into the new row – read the question carefully!

Linear Search has two main advantages in certain situations. Firstly, it does not require the data to be sorted, which is a significant pre-requisite for Binary Search. Sorting a list takes time, and if you only need to search the list once, it might be faster overall to just do a linear search. Secondly, it is very simple to implement.

Yes, many. Bubble Sort is taught because it is simple to understand, but its $O(n^2)$ time complexity makes it very inefficient for large lists. More advanced algorithms like Merge Sort and Quick Sort have an average time complexity of $O(n \log n)$, making them vastly superior for practical use.

No, you should not use a specific programming language like Python or Java unless explicitly asked. The standard ways to express an algorithm are through structured English, flowcharts, or, most commonly, pseudocode. The Cambridge syllabus provides a standard for pseudocode that you should learn and use.

Worst-case complexity ($O$) describes the maximum number of steps an algorithm might take for a given input size 'n'. For a linear search, this is finding the item at the very end. Average-case describes the expected performance across all possible inputs. While both are important, A-Level focuses primarily on understanding and comparing worst-case complexities.