GCSE Link: None
The time complexity of an algorithm is a way of expressing how the performance of the algorithm scales as the input gets bigger.
We use Big O Notation to describe the time complexity of an algorithm. To do this, we look at the
number of steps the algorithm takes relative to the size of the input, n.
Then, we ignore everything except the largest term, and remove all constant factors. For
example, 0.5n2 + 2n - 3 becomes simply n2.
A constant time algorithm takes the same amount of time to complete regardless of the input.
An example of a constant time algorithm would be getting the first element of an array. This is
because no matter how long the array is, the subroutine will complete in the same amount of
time. This is written as O(1) in Big O Notation.
Example 1 shows an algorithm to retrieve the first element of an array.
Example 1
SUBROUTINE FirstItem(arr)
RETURN arr[0]
ENDSUBROUTINE
A logarithmic time algorithm halves the size of the problem at every step.
An example of a logarithmic time algorithm would be converting a number to binary. This is
because doubling the input number adds one extra step that needs to be completed. This is written
as O(log n) in Big O Notation.
Example 2 shows an algorithm to convert a number into binary.
Example 2
SUBROUTINE ToBinary(num)
IF num < 2 THEN
RETURN STR(num)
ENDIF
RETURN ToBinary(num DIV
2) + STR(num % 2)
ENDSUBROUTINE
A linear time algorithm takes twice as long to complete if you double the input size.
An example of a linear time algorithm would be calculating the sum of an array. This is
because there is a FOR loop which iterates through the whole array, so the time
taken will be more or less proportional to the size of the input. This is written as
O(n) in Big O Notation.
Example 3 shows an algorithm to find the sum of an array.
Example 3
SUBROUTINE Sum(arr)
result ← 0
FOR i ← 0 TO
LEN(arr)-1
result ← result + arr[i]
ENDFOR
RETURN result
ENDSUBROUTINE
A quadratic time algorithm takes four times as long to complete if you double the input size.
An example of a quadratic time algorithm would be finding all distinct pairs in an array. This is
because there is nested iteration which goes through the array twice, so the time taken
will be more or less proportional to the size of the input squares. This is written as
O(n2) in Big O Notation.
Example 4 shows an algorithm to find all distinct pairs of elements in an array.
Example 4
SUBROUTINE FindAllPairs(arr)
result ← []
FOR i ← 0 TO
LEN(arr)-2
FOR j ← i+1
TO LEN(arr)-1
result.Append([arr[i], arr[j]])
ENDFOR
ENDFOR
RETURN result
ENDSUBROUTINE
An exponential time algorithm takes significantly longer to complete when you make the input bigger.
An example of a exponential time algorithm would be finding all subsets of an array. This is
because the total number of subsets in an array of length n is
2n. This is written as O(2n)
in Big O Notation.
Example 5 shows an algorithm to find all distinct pairs of elements in an array.
Example 5
SUBROUTINE Subsets(arr)
result ← []
FOR mask ← 0 TO
2**LEN(arr)-1
subset ← []
FOR i ← 0
TO LEN(arr)-1
IF (mask >> i) & 1 THEN
subset.Append(arr[i])
ENDIF
ENDFOR
result.Append(subset)
ENDFOR
RETURN result
ENDSUBROUTINE
What is the time complexity of an algorithm to find the maximum item of an array?
O(n), because you would have to go through each item (just like the
Sum function in Example 3). Therefore that algorithm has a linear time
complexity.