‹ Back to the paper
Question 2(e)
2 marks
Computer ScienceISC 2020 Specimen Computer Science Paper 1Short answerComplexity and Big O notation
Answer the following in short.
Define Big ‘O’ notation. State the two factors which determine the complexity of an algorithm.
Answer
Answer
Big 'O' notation is a mathematical notation that describes the limiting behaviour of an algorithm: it gives the upper bound on the growth of the running time (or memory) of the algorithm as a function of the input size $n$ (the worst case), ignoring constants and lower-order terms.
The two factors that determine the complexity of an algorithm are:
1. Time complexity: the amount of time (number of basic operations) the algorithm takes, as a function of the input size.
2. Space complexity: the amount of memory the algorithm needs, as a function of the input size.