Classification of algorithms study guide

1. Start with the problem size

When analysing an algorithm, define n as the size of the problem. This might represent the number of values, objects or other input elements being processed. Ask how the number of operations changes when n increases. The specification emphasises that problem size is the key issue, so an explanation based only on a small example is incomplete.

2. Derive the growth rate

Count the structure of the algorithm rather than trying to calculate an exact execution time. If a fixed sequence of instructions is performed regardless of n, the time complexity is O(1). If one action is performed for every input element, the complexity is O(n). If work is organised in two dependent levels, each potentially involving n items, the complexity can be O(n²), which is polynomial. If the number of possibilities follows a form such as 2ⁿ, the complexity is exponential. If the number of steps grows according to a logarithmic function, the complexity is logarithmic.

For exam reasoning, state the source of the growth. For example: “The operation is repeated once for each of the n input items, so the running time grows linearly and is O(n).” For nested repetition, explain that the first level can execute n times and the second can also execute n times, giving a growth proportional to n × n, or O(n²). This is a derivation of the time complexity rather than an unsupported label.

3. Compare time and space separately

An algorithm may be more efficient time-wise than another, or more efficient space-wise. These are different comparisons. Time complexity concerns how running-time requirements grow; space efficiency concerns the memory resources required. When answering a comparison question, identify which resource is being discussed and avoid claiming that an algorithm is generally “more efficient” without specifying the basis.

4. Apply tractability carefully

A problem is tractable when it has a polynomial-or-less time solution. Constant, logarithmic and linear growth are no greater than polynomial growth, and polynomial examples such as O(n²) are also tractable. Exponential growth is not polynomial growth, but the classification in the specification is about whether a polynomial-or-less solution exists for the problem, not merely about the label attached to one attempted algorithm. A problem with no polynomial-or-less time solution is intractable. Heuristic methods are often used for such problems, but this does not change the definition of tractability.

5. Distinguish limits of efficiency from limits of computation

Hardware and algorithmic complexity can limit what is practical to compute. This is different from a problem being non-computable. An intractable problem concerns the absence of a polynomial-or-less time solution. A non-computable problem is one that cannot be solved algorithmically. The Halting problem is the required example: it asks whether any program will eventually stop for particular input, and it is unsolvable. Its importance is that it establishes that some problems cannot be solved by a computer, rather than merely being slow on available hardware.

6. Self-check questions

Can you define n for a given algorithm? Can you explain why a fixed amount of work is O(1), why repeated work over the input is O(n), and why two dependent levels can give O(n²)? Can you distinguish time efficiency from space efficiency? Can you define tractable and intractable without equating intractable with non-computable? Finally, can you describe the Halting problem and state its significance without attempting to prove it? Strong answers use the growth of a function, the size of the problem and the exact classification being tested.