Question 1

If Binary Search is so much faster, why would anyone use Linear Search?

Accepted Answer

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.

Question 2

Are there better sorting algorithms than Bubble Sort?

Accepted Answer

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.

Question 3

How do I write algorithms in the exam? Do I need to use a specific programming language?

Accepted Answer

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.

Question 4

What's the difference between worst-case and average-case complexity?

Accepted Answer

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.

Algorithms

What you need to know

Computer Recipes: Searching and Sorting